We are given a natural number $x\in\mathbb{N}^+$, and $x-1$ adders. An adder in our case would be a component with two inputs $x_1,x_2$ and a single output $y$ such that $y=x_1+x_2$. Our goal is to design a system that has $x$ as its single input, and $x^2$ as its single output. No constants are available to use. Define $n:\mathbb{N}^+\to\mathbb{N}$ such that $\forall x\in\mathbb{N}^+$, $n(x)$ is the minimum amount of adders needed in order to implement such system that calculates $x^2$. What is $n(x)$ precisely?
For example: In order to calculate $7^2$ efficiently:
- First step: we only have $7$, so we must do $7+7=14$. (1 adder)
- Second step: Now we also have $14$, so we can calculate $7+14=21$ and $14+14=28$ (2 adders; 3 overall)
- Final step: Now we have $21$ and $28$, so we can calculate $21+28=49$ (1 adder; 4 overall) and we're done.
It needs to be proven now that $7^2$ can't be calculated using $3$ adders or less (pretty intuitive), and then it can be concluded that $n(7)=4$.
It is clear that $n(x)\leq x-1$. I was able to show that $n(x)$ is not increasing (for instance - $n(7)=4$ while $n(8)=3$), but I think I did manage to find a tighter upper bound - which is $n(x)\leq2\lfloor\log_2(x)\rfloor$. I'm having trouble with finding the exact expression for $n(x)$.
This was my way of thinking. For every $m\in\mathbb{N}^+$, define the group of natural numbers $A_m$ s.t.:
$$A_m\triangleq \{x\in\mathbb{N}^+|\lceil\log_2(x)\rceil=m\}$$
So for example, $A_3=\{5,6,7,8\}$. It is clear that $x_m\equiv2^m-1\in A_m$. This demands proof, but I tend to believe that out of all the integers of $A_m$, $x_m$ requires the greatest amount of adders. Pay attention that:
$$x_m^2=x_m(2^{m-1}+2^{m-1}-1)=2^{m-1}x_m+\sum_{k=0}^{m-2}2^kx_m$$
You can efficiently calculate $2^{m-1}x_m$ using $m-1$ adders. When you do that, you have the input $2^kx_m$ available, for every $k\in[1,m-1]_\mathbb{N}$. So $\sum_{k=0}^{m-2}2^kx_m$ can be calculated with $m-2$ adders. Then, a final adder is needed in order to calculate $x_m^2$. So overall:
$$n(2^m-1)=2m-2$$
Given that $x_m^2$ cannot be calculated using $2m-3$ adders or less. Pay attention that for $m=3$, we get $n(7)=4$, as before.
I tried to do the same thing with different patterns, but I didn't manage to conclude the general form. Some help would be appreciated :)
Note: This question can be rephrased in a clearer way. Suppose you initially have a set $S=\{1\}$, each time you can pick up two (can be duplicate) numbers in $S$ and put the sum of those two numbers in $S$. What is the least number of steps, or $|S|$, that is needed such that $n\in S$? (The question is not the same, but the answers are (I believe) the same, since all my equations can simply be divided by $x_m$). (Thank you @JetfiRex for this)
Not really an answer, but you can refer to wiki page and oeis to find the thing you need...
Also, this is the result by running the python code below:
The result is here: (covers at least 1 to 378)