# Can $2^n$ and $2^{n+1}$ have the same digit sum?

For $n\in\mathbb{N}^*$ we note $s(n)$ the sum of the digits of $2^n$. For example $s(4)=7$ because $2^4=16$. Is it possible to find an integer $n$ such that $s(n)=s(n+1)$?

-
all $n \ge 0$ when in binary ;) – ratchet freak Oct 12 '11 at 15:06

No, because the digit sum for $k$ is congruent to $k$ modulo 3, and $k$ and $2k$ are only congruent mod $3$ if $k$ is divisible by $3$.

-
Using the standard casting out $9$s, we have same thing mod $9$. (+1) – robjohn Oct 12 '11 at 4:37

HINT $\$ More generally, just as in casting nines, by casting $\rm\:b-1$'s in radix $\rm\:b\:$ we conclude that if $\rm\ 2^{n+1}\:$ and $\rm\:2^{n}\:$ have equal radix $\rm\:b\:$ digit sums then $\rm\: b-1\ |\ 2^{n+1}-2^n = 2^n\:,\:$ hence $\rm\:b = 2^k+1\:.$

For example, in radix $5$ note that $\ 2^2 = 4,\ 2^3 = 13,\ 2^4 = 31\:$ all have digit sum $\:= 4\:,\:$ and, similarly, in radix $9\!:\ \:2^3 = 8,\ 2^4 = 17,\ 2^5 = 35,\ 2^6 = 71,\ 2^7 = 152\$ all have digit sum $\:= 8\:.$

Even more generally, a result analogous to that above remains true if we replace $2$ by any prime $\rm\:p\:$ such that $\rm\: \gcd(p-1,b-1) = 1\:.$

-
Thanks for the example. At first, I thought you were saying something else, until I thought more about it. (+1) – robjohn Oct 12 '11 at 4:48

No: $2 \equiv -1 \pmod 3$, so $2^n \equiv (-1)^n \pmod 3$, and therefore the sequence $\langle 2^n:n\in\mathbb{N}^*\rangle$ is $\langle -1,1,-1,1,\dots\rangle$ when reduced mod $3$.

-