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.