1
$\begingroup$

I've been trying to figure out a way to recursively divide a number by 2 until that operation would no longer result in a whole number (without actually running through such a process manually; i.e. find an equation that would just tell me).

From what I've been testing, it looks like when you take a number and keep subtracting the highest power of 2 possible without dropping below 0, the exponent of the last power is the same as the number of times you can recursively divide by 2 while still getting a whole number.

For example:

$24 - (2^4) - (2^3) = 0 $ ($3 $ being the exponent of the last power)

$\frac{24}{ 2} = \frac{12}{2} = \frac{6}{ 2} = 3$ ($3$ being the number of times you can recursively divide by $3$ (or its count of $2$'s in its prime factorization))

Why is this the case? I know if you factor out as many $2$'s as possible while keeping whole numbers from the 'subtracting powers' example above you get $(2^3)(2+1)$, so it seems that this process is just another way to get prime factorization; but that just seems like such an unsatisfying answer. I'm really hoping there is some deeper meaning to be had here.

Can anyone here give me the rundown on this or point me in the direction of some reading on this topic?

$\endgroup$
1
$\begingroup$

What a neat discovery. The key is that every natural number can be written as a sum of powers of two. For all $n$, there exist powers $r_1, r_2, \dots, r_k$, such that $$ n = 2^{r_1} + 2^{r_2} + \dots + 2^{r_k} $$ Arrange these powers in increasing order, so that $r_1$ is the smallest. That is your “exponent of the last power” from your experimentation. On the other hand, since all the other powers are higher than $r_1$, all the other terms in the sum are divisible by $2^{r_1}$. Therefore $$ n = 2^{r_1}\left(1 + 2^{r_2 - r_1} + 2^{r_3 - r_1} + \dots + 2^{r_k - r_1}\right) $$

You can see that after dividing $n$ by $2$ $r_1$ times, the remainder is the sum of a bunch of powers of $2$, plus one. That is, the remainder is no longer divisible by $2$. Therefore, $r_1$ is also the largest number of times you can divide $n$ by before reaching an odd number.

$\endgroup$
4
  • $\begingroup$ Re your third sentence, yeah, but the representation isn't unique; we can also write $24=2^0+\cdots+2^0$, in which case the rest of your answer doesn't make sense. $\endgroup$ – symplectomorphic Sep 10 '19 at 0:55
  • $\begingroup$ @symplectomorphic Guess I was being sloppy. I meant to refer to binary representation. For any $n$ there exist unique powers $r_1 < r_2 < \dots < r_k$ such that $n = 2^{r_1} + \dots + 2^{r_k}$. Is that not correct? $\endgroup$ – Matthew Leingang Sep 10 '19 at 1:37
  • $\begingroup$ @MatthewLeingang Thank you for your answer. Would it be too much trouble if I shot you a message with some clarification? I promise I won't take up too much of your time. I'm just trying to get some deeper understanding of a project before moving on to the next thing. $\endgroup$ – JohnDNoone Sep 11 '19 at 0:27
  • $\begingroup$ @JohnDNoone I'm glad it helped. It would be better if you just kept posting here. There are plenty in the community who can answer well-posed questions. MSE is my procrastination device, so I shouldn't let it bring me extra work. :-) $\endgroup$ – Matthew Leingang Sep 11 '19 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.