# Is it true that for infinitely many values of $n$, the sum of digits of $2^n$ is greater than for $2^{n+1}$?

Let $S(n)$ denote the digit sum of the integer $n$, using base $10$. How to prove that there exist infinitely natural numbers such that $S(2^n)>S(2^{n+1})$?

Remarks (by Deven Ware):

1. This is not true in base $2$, because then the sum of digits is always $1$.

2. $S(2^n)$ is never equal to $S(2^{n+1})$ because the powers differ $\bmod 3$.

• Definitely not in base $2$ :) Commented Nov 10, 2013 at 1:50
• @user107678 both are 1 always. Commented Nov 10, 2013 at 2:26
• I'm not sure how to finish this one, but the following observation is likely relevant. Consider the digits of $2^n$. We can predict the relative change $S(2^{n+1})-S(2^n)$ from the digits in the following way: for a digit of 0, no change; digit of 1 gives +1; digit of 2 gives +2; 3 gives +3, 4 gives +4, 5 gives -4, 6 gives -3, 7 gives -2, 8 gives -1, 9 gives no change. So you need some way of predicting a glut of digits 5-8 over digits 1-4, in an appropriate weighting, but I'm not seeing any pattern that lasts indefinitely. Commented Nov 10, 2013 at 3:54
• Another thing I have noticed is that $2^n$ and $2^{n+1}$ cannot have the same digit sum as they are different modulo 3. So if we do not have this property, then we have the digit sums strictly increasing eventually. Commented Nov 10, 2013 at 4:19
• @JonasMeyer Only for beings with ten fingers. Commented Jul 26, 2014 at 18:27

Expanding on Deven Ware's observation: assuming $S(2^n)$ is eventually nondecreasing, not only would it strictly increase, but we can give a non-trivial lower bound on its rate of growth.

Working mod $3$, for instance, note that if for some $m$, $S(2^m) \equiv 2 \pmod 3$, then $S(2^{m+1}) \equiv 1 \pmod 3$, so if $S(2^{m+1}) > S(2^m)$ then in fact $S(2^{m+1}) \ge S(2^m)+2$. We can easily see this leads a lower bound of $$S(2^n) \ge \tfrac32 n + O(1),$$ which is stronger than the $n+O(1)$ lower bound one gets from just being strictly increasing.

On the other hand, since $2^n$ has $\frac{\log 2}{\log 10}n + O(1)$ digits, we have an upper bound of $$S(2^n) \le 9\frac{\log 2}{\log 10}n + O(1) < 2.71n + O(1).$$ This doesn't contradict our lower bound of $S(2^n) \ge \tfrac32 n + O(1)$, but look at what happens when we work modulo $9$ instead:

The sequence $\{2^n\}$ cycles modulo $9$ as $1,2,4,8,7,5,1,\ldots$, and $\{S(2^n)\}$ follows exactly the same cycle. However, if we assume $S(2^n)$ is (eventually) nondecreasing, then starting from any sufficiently large $m$ such that $S(2^m) = 9k+1$, we have the chain of inequalities:

\begin{align} S(2^{m+1}) &\ge 9k+2, \\ S(2^{m+2}) &\ge 9k+4, \\ S(2^{m+3}) &\ge 9k+8, \\ S(2^{m+4}) &\ge 9k+16, \\ S(S^{m+5}) &\ge 9k+23, \\ S(S^{m+6}) &\ge 9k+28, \end{align}

which yields a lower bound of $S(2^n) \ge \frac{27}{6} n + O(1) = 4.5n + O(1)$. This does contradict the upper bound from the number of digits, so indeed $S(2^n)$ must decrease infinitely often.

What homework is this from? This is actually quite a pretty question, and I'm both pleased and impressed that it can be answered by such elementary methods.

• Can you solve this for $3^n$?
– Andy
Commented Oct 31, 2017 at 20:42
• @Andy It should be easy to show that $S(3^n) \ge S(3^{n+1})$ infinitely often, however I don't see a way to rule out $S(3^n) = S(3^{n+1})$ because both sides are generally congruent mod $9$. Commented Nov 1, 2017 at 15:35
• they're actually even congruent as numbers many times :)
– Andy
Commented Nov 2, 2017 at 16:38