For a positive integer $k$, let $s(k)$ denote the sum of the digits of $k$. Show that there are infinitely many natural numbers $n$ such that $s(2^n) > s(2^{n+1})$.
Problem
Source:
Tags: logarithms, modular arithmetic, number theory unsolved, number theory
17.01.2015 22:59
For a positive integer $k$ written with $d$ digits, thus $10^{d-1} \leq k < 10^d$, we have $s(k) \leq 9d \leq 9(\log_{10} k + 1)$. Therefore we must have $s(2^n) \leq 9(n\log_{10} 2 + 1)$. On the other hand, we have $s(k) \equiv k \pmod{9}$. The residues modulo $9$ of the numbers $2^n$ cycle as $1,2,4,8,7,5,1,2,\ldots$, and of course, the residue modulo $9$ of $2^{n+1}$ is twice that of $2^n$. Assume there exists $n_0$ such that $s(2^n) \leq s(2^{n+1})$ for all $n\geq n_0$. Take some fixed $n=6m \geq n_0$, thus with $s(2^n) \equiv 2^n \equiv 1\pmod{9}$. In order for the sum of digits not to decrease, we need it to increase by at least $1,2,4,8,7,5$ respectively, for the residues $1,2,4,8,7,5$. Therefore $s(2^{n+6}) \geq 1 + 2 + 4 + 8 + 7 + 5 + s(2^n) = 27 + s(2^n)$. Iterating this argument, we get $s(2^{n+6t}) \geq 27t + s(2^n) > 27t$ for all positive integers $t$. But $s(2^{n+6t}) \leq 9((n+6t)\log_{10} 2 + 1) =$ $ 9(n\log_{10} 2 + 1) + (54\log_{10} 2)t <$ $ 9(n\log_{10} 2 + 1) + 17t$. We thus obtain that $9(n\log_{10} 2 + 1) + 17t > 27t$, i.e. $9(n\log_{10} 2 + 1) > 10t$ for all positive integers $t$, obviously absurd. Notice also that since never $s(2^n) = s(2^{n+1})$, a similar, but much simpler, argument shows that infinitely often we have $s(2^n) < s(2^{n+1})$.