12
$\begingroup$

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$.

$\endgroup$
11
  • 3
    $\begingroup$ Definitely not in base $2$ :) $\endgroup$
    – chubakueno
    Commented Nov 10, 2013 at 1:50
  • 1
    $\begingroup$ @user107678 both are 1 always. $\endgroup$
    – Deven Ware
    Commented Nov 10, 2013 at 2:26
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 10, 2013 at 3:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Deven Ware
    Commented Nov 10, 2013 at 4:19
  • 1
    $\begingroup$ @JonasMeyer Only for beings with ten fingers. $\endgroup$ Commented Jul 26, 2014 at 18:27

1 Answer 1

23
+100
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you solve this for $3^n$? $\endgroup$
    – Andy
    Commented Oct 31, 2017 at 20:42
  • $\begingroup$ @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$. $\endgroup$
    – Erick Wong
    Commented Nov 1, 2017 at 15:35
  • $\begingroup$ they're actually even congruent as numbers many times :) $\endgroup$
    – Andy
    Commented Nov 2, 2017 at 16:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .