Factoring a number in the format $2^x + 2^y...$, etc.

46 Views Asked by At

Lets say I have this number: $4294967296$. I can easily convert it to $2^{32}$.

Now lets say I have this number: $33554688$. How could I factor it into $2^{25} + 2^8$? It needs to always be in the format of ($2$ to the power of $x$).

From my understanding every number could be factored into this format(unless it's odd then it would need a $+1$ at the end).

1

There are 1 best solutions below

0
On

There might be a faster method than this, but this method should work.

First, let's call your target number $N$. Start by finding the largest power of $2$ that is less than or equal to $N$, which in this case is $2^{25}=33554432$. Finding that first power of $2$ might be a little tedious if you do it by hand, but there are ways around that. Once you've found that power of $2$, subtract it from $N$ and repeat the process.

In this case, you find that $N-2^{25}=256$, which is clearly recognizable as $2^8$. Then you can rewrite the last equation and solve for $N$, and you're done:

\begin{align} N-2^{25}&=256 \\ N-2^{25}&=2^8 \\ N&=2^{25}+2^8 \end{align}