# Summing digits of powers of 2 to get 1 2 4 8 7 5 pattern

If you add the decimal digits of multiples of 9,possibly repeatedly, you get 9. For instance, with 18 we have $$18\mapsto 1+8=9$$ and with 909 we have $$909\mapsto 9+0+9=18\mapsto 1+8=9.$$ This is proven.

If you do the same with powers of two, you develop a repeating pattern, 1,2,4,8,7,5, even when you descend negative powers. I don't know if this stops eventually, but it seems like there might be a proof for it. Can anyone prove this?

\begin{align*} .0625\mapsto 6+2+5=13&\mapsto 4 \\ .125&\mapsto 8 \\ .25 &\mapsto 7 \\ .5 &\mapsto 5 \\ 1&\mapsto 1 \\ 2 &\mapsto 2 \\ 4 &\mapsto 4 \\ 8&\mapsto 8 \\ 16&\mapsto 7 \\ 32&\mapsto 5 \\ 64\mapsto 10 &\mapsto 1 \\ 128&\mapsto 2 \\ 256 \mapsto 13 &\mapsto 4 \\ 512 &\mapsto 8 \\ 1024 &\mapsto 7 \\ 2048 \mapsto 14&\mapsto 5 \\ 4096\mapsto 19 &\mapsto 1 \\ \end{align*}

-

We look at $2^n$, where $n$ ranges over the non-negative integers.

The key is the fact that $2^6$ has remainder $1$ on division by $9$. Using congruence notation, we have $2^6\equiv 1\pmod{9}$. Let $n$ be any non-negative integer. We can express $n$ as $6q+r$, where $0\le r\le 5$ ($q$ stands for quotient, $r$ for remainder).

It follows that $$2^n=2^{6q+r}=(2^6)^q 2^r\equiv (1)^q 2^r\equiv 2^r\pmod{9}.$$ So the remainder when you divide $2^n$ by $9$ depends only on $r$. For $r=0$, $1$, $2$, $3$, $4$, and $5$, these remainders are, as you observed, $1$, $2$, $4$, $8$, $7$, and $5$.

To connect this with sums of (decimal) digits, observe that a decimal number like $6852$ is just $(6)(10^3)+(8)(10^2)+(5)(10^1) +(2)(10^0)$. But for any non-negative integer $k$, we have $10^k\equiv 1\pmod{9}$. So $6852\equiv 6+8+5+2 \pmod{9}$. Thus the remainder when $6852$ is divided by $9$ is the same as the remainder when $6+8+5+2$ is divided by $9$. Asimilar remark holds for any non-negative integer expressed in decimal form.

Since remainders when $2^n$ is divided by $9$ cycle with period $6$, and the "casting out nines" process gives us these remainders, the pattern you observed continues forever.

You extended the pattern to negative exponents. This is an interesting observation that I do not recall seeing before. Express $2^{-n}$ as a decimal, by noting that $$2^{-n}=\frac{1}{2^n}=\frac{5^n}{10^n}.$$ Then (essentially) you looked at the digit sum (modulo $9$) of $5^n$. Modulo $9$, the numbers $5^n$ cycle with period $6$, for the same reason as with $2^n$.

Now calculate $5^n$ modulo $9$, for $n=0,1, 2, 3, 4, 5$. We get that $5^n$ is congruent in turn to $1$, $5$, $7$, $8$, $4$, and $2$ modulo $9$. So the pattern does indeed continue "backwards."

Remark: For a more general approach, please see Euler's Theorem.

-
You don't actually need to compute the same thing for $5^n$. Just note that 2 and 5 are inverses mod 9. – ronno Aug 21 '12 at 7:30
Thanks for the comment. I was dissatisfied with my answer, still am, was and am uncertain about appropriate level. – André Nicolas Aug 21 '12 at 8:39