# Indices and powers of 2.

To find the value of $x^8$ given $x$, you need three arithmetic operations: $x^2=x\times x$, $x^4$=$x^2 \times x^2$ and $x^8=x^4\times x^4$. To find $x^{15}$, five operations will do: the first three of them are the same; then $(x^{16})=(x^8)\times (x^8)$ and $(x^15)=(x^{16})/x$ . What is the minimum number of operations (multiplications and divisions) will be needed to find the value of $x^{1000}$?

I tried solving this problem logically as follows :

for $(x^8) \Rightarrow 3=3+0$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)->/(x^0) = (x^8)$

for $(x^{15}) => 5=4+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})->/(x^1) = (x^15)$

for $(x^{30}) => 6=5+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})->(x^{32})->/(x^2) = (x^{30})$

for $(x^{61}) => 7=6+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})->(x^{32})->(x^{64})->/(x^3) = (x^{61})$

for $(x^{124}) => 8=7+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})->(x^{32})->(x^{64})->(x^{128})->/(x^4) = (x^{124})$

for $(x^{251}) => 9=8+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})->(x^{32})->(x^{64})->(x^{128})->(x^{256})->/(x^5) = (x^{251})$

for $(x^{506}) => 10=9+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})\rightarrow(x^{32})\rightarrow(x^{64})\rightarrow(x^{128})\rightarrow(x^{256})\rightarrow(x^{512})\rightarrow/(x^6) = (x^{506})$

for $(x^{1017}) => 11=10+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})\rightarrow(x^{32})\rightarrow(x^{64})\rightarrow(x^{128})\rightarrow(x^{256})\rightarrow(x^{512})->(x^{1024})\rightarrow/(x^7) = (x^{1017})$

for $(x^{2048}) => 12=11+1$ operations : $(x^2)\rightarrow(x^4)\rightarrow(x^8)\rightarrow(x^{16})\rightarrow(x^{32})\rightarrow(x^{64})\rightarrow(x^{128})\rightarrow(x^{256})\rightarrow(x^{512})\rightarrow(x^{1024})\rightarrow(x^{2048})/(x^8) = (x^{2048})$

By this approach, I do not get $x^{1000}$. Please advise.

• in your route to $x^{61}$, why is division by $x^3$ counted as just one operation ? Even if you store the value of $x^2$, don't you need one multiplication to get $x^3$, and then the division, which makes two operations, giving a total of 8 ? – gandalf61 Jun 26 '18 at 9:24
• There's a variation of this called "addition chains" where there are unsolved problems, so this one is probably not easy (in general, that is – it may not be that hard for 1000, I don't know). But I'd advise calculating the first 10 values and then consulting the OEIS. – Gerry Myerson Jun 26 '18 at 9:28
• The somewhat straightforward approach would be to compute $$x^2,x^4,x^8,x^{16},x^{32},x^{64}, x^{128}, x^{256}, x^{512}$$ by repeated squaring (9 operations). Then multiply $$x^{512}x^{256}x^{128}x^{64}x^{32}x^8=x^{1000}$$ (another 5 operations) for a total of $14$ operations. But you could also compute $x^2, x^4, x^8$, and $x^{10}$ in four operations, then similarly $x^{100}=(x^{10})^{10}$ and $x^{1000}=(x^{100})^{10}$ in eight more operations for a total of $12$ operations. (Still not using divisions). The proof that 11 ops are not enough may be a bit convoluted ... – Hagen von Eitzen Jun 26 '18 at 9:28
• Isn't this isomorphic to getting $1000$ using only $1,+,-,*$? Might be easier to think about in this form. – hyperpallium Jun 26 '18 at 9:36
• Thank You @HagenvonEitzen ... The total of 12 operations, did help to get (x^1000). ... but, I am confused if the question is trying to presenting some pattern by showing (x^8) and (x^15) operations? – Math Tise Jun 26 '18 at 10:30