pattern when dividing natural numbers by 2

Question

There occurs a pattern which I cannot describe when you keep dividing natural number by 2. It gets separated in two groups; one which the ones are ...25 and the other which ones are ...75. For example numbers 2, 4, 5, 8, 9, 13 etc. are in first group and number 3, 6, 7, 11, 12, 14, 15 etc. in the other.

Answer 1

Nice observation! We can write every natural number $n$ in the form $2^k o$ where $o$ is odd; we might call $o$ the "odd part" of $n$. The first set of natural numbers is the set such that $o \equiv 1 \bmod 4$ (this is modular arithmetic notation, it just means that $o = 4k + 1$ for some integer $k$), and the second set of natural numbers is the set such that $o \equiv 3 \bmod 4$. That is:

Claim: If $o \equiv 1 \bmod 4$, then the decimal expansion of $\frac{o}{2^i}$ ends $\dots 25$ for any $i \ge 2$, and if $o \equiv 3 \bmod 4$, then the decimal expansion of $\frac{o}{2^i}$ ends $\dots 75$ for any $i \ge 2$.

Proof. The last two digits of the decimal expansion are given by

$$10^i \frac{o}{2^i} \bmod 100 = 5^i o \bmod 100.$$

So it suffices to understand the last two digits of powers of $5$ times an odd number. If $i \ge 2$ then $5^i$ is always a multiple of $25$, so $5^i$ times an odd number must either be $25 \bmod 100$ or $75 \bmod 100$. It's also not hard to see that the answer only depend son the value of $o \bmod 4$, since $100 = 25 \cdot 4$. Then we just check that when $o = 1$ we get $25$ and when $o = 3$ we get $75$, as desired. $\Box$

There are further patterns if you look at the last $3$ digits when $i \ge 3$ depending on the value of $o \bmod 8$ and so on and so forth.

Answer 2

If you write your integer in base $2$ it is represented by a sequence of $0$ and $1$.

Dividing by $2$ just moves the comma to the left, so let's divide by $2^i$ until there are exactly two digits behind the comma (trailing zeros excluded).

e.g. $n=34=\overline{100010}_2\ $ gives $\ \overline{100,01}_2$ after division by $8$.

These digits can only be $01$ or $11$ (since $\overline{0,10}_2=\overline{0,1}_2$ and $\overline{0,00}_2=\overline{0}_2$ have only zero or one digit behind the comma).

Therefore either :

• $\dfrac n{2^i}=m+\overline{0,01}_2=m+\frac 14\quad$ or
• $\dfrac n{2^i}=m+\overline{0,11}_2=m+\frac 34$

Note: $n=2^{i-2}\,o$ with $o=4m+1$ or $o=4m+3$ as in Q.Yuan presentation.

Now we shall see that dividing by another factor of $2$ does not change the pattern, indeed dividing by $2$ is equivalent to a multiplication by $5$ followed by a division by $10$.

• $\dfrac n{2^{i+1}}=\dfrac 1{10}\cdot(5m+\frac 54)=\dfrac 1{10}(5m+1+\frac 14)=\dfrac 1{10}(m'+\frac 14)\quad$ or
• $\dfrac n{2^{i+1}}=\dfrac 1{10}\cdot(5m+\frac {15}4)=\dfrac 1{10}(5m+3+\frac 34)=\dfrac 1{10}(m'+\frac 34)$

The division by $10$ just moves the comma in the decimal representation, so the last two digits are unaffected and are these of $\frac 14$ or $\frac 34$ (i.e. $25$ or $75$).

Since the pattern is stable, you can divide by $2$ any number of times.