Find all positive integers $n$ such that sum of digits of $2^n$ is equal to $n$.

For example, $2^5=32$ and $3+2=5$. Similarly, it can be shown that it works for $2^{70}$. Using basic results in modular arithmetic, one can show that $n$ has to be either of the form $18k+5$ or $18k+16$, where $k$ is non-negative integer. The two examples satisfy the form (for $k=0$ and $k=3$) but I was not able to find other examples. I do know that $2^n$ has $\left \lfloor n\cdot \log_{10}2\right \rfloor+1$ digits which, coupled with the fact that average digit value is $4.5$, implies that the average digit sum is about $1.35n$. Clearly, this is much larger than $n$ (for large $n$) so it may be that no other $n$ satisfies the question I posed.

Any ideas how to proceed?

• I have no idea if this is hard enough for number theory so I have tagged it with elementary number theory. I have also found the sequence here oeis.org/A001370 . – PowerDigitSumGuy Jul 16 '14 at 6:15
• The only $n\le 100000$ are $5$ and $70$. – lhf Jul 16 '14 at 6:43
• You analysis seems right. The sum seems to oscillate closely around $1.35n$. – lhf Jul 16 '14 at 6:46
• I've run a program. – lhf Jul 16 '14 at 6:51
• The same analysis seems to work for other bases, except $10$, of course. – lhf Jul 16 '14 at 7:16

Here are the heuristic considerations:

Suppose for each positive integer $n$ you took $c n$ iid random variables $X_i(n)$ (where $4.5 c > 1$), each having values $0,\ldots,9$ with equal probability, and let $S_n$ be their sum. According to Cramer's Theorem from the theory of Large Deviations, $\log P(S(n) \le n)$ is asymptotic to a negative constant times $n$ (where the constant can be computed, but I won't bother). In particular $\sum_{n=1}^\infty P(S(n) \le n) < \infty$. Then, according to Borel-Cantelli, almost surely only finitely many of the events $S_n \le n$ occur. With a bit more work you can estimate the expected number of occurrences.

Of course the digits of powers of $2$ are not really random, but it's quite reasonable to expect, on this basis, that there are only finitely many $n$ for which the sum of the digits of $2^n$ is at most $n$.

• I see the idea but I have this question: where is the "breaking point" in the following sense: using this argument we can start making digit sum closer to the average and keep increasing number of solutions. Surely, eventually we have to have infinite number of solutions. Does this happen when the summation you mention become infinite? I ask this because it seems to me that it is key to compute P's AND show their sum is finite. – PowerDigitSumGuy Jul 16 '14 at 8:17
• The other part of the Borel-Cantelli lemma says that if $E_n$ are independent events with $\sum_n P(E_n) = \infty$, then almost surely infinitely many of them occur. – Robert Israel Jul 16 '14 at 15:17
• Benford's law (applicable for leading digit of $2^n$) gives that digits are not uniformly distributed for the leading digit. Later digits, while getting close to uniform, are not exactly uniformly distributed. Paper I found by T. Hill mentioned also that digits are NOT independently distributed. But let's say that we can somehow overcome these issues and apply some version of Cramer's theorem which does not need IID assumption to show that sum you mention is finite. How do we then know where these finite cases are (i.e. how do we know $n=70$ is the last case?) – PowerDigitSumGuy Jul 18 '14 at 18:20
• We don't. The most we can do is estimate the expected number of additional cases. – Robert Israel Jul 18 '14 at 22:23
• BTW you might also mention some reasons the digits are not independent: their sum mod 9 is known, as is their alternating sum mod 11. – Robert Israel Jul 18 '14 at 22:25

Not an answer, but I wanted to share a graph of the sum of digits $a(n)$ divided by $n$. As can be seen below, it clusters nicely around $1.35n$, which confirms your analysis.

OEIS says "it is believed that $a(n) \sim n \cdot (9/2)\log_{10}2$, but this is an open problem". Of course, you don't need this in full to prove what you want, just that $a(n) > 1.2 n$ (for instance) for $n>70$.

$\hbox{}\quad$

• I do have have an idea how to derive the probability of $1.35\cdot n$ digit number having sum of digits equal to $n$ but I don't want to proceed since I am not sure what to do if I have that probability. Essentially, this probability will (I expect) approach $0$ exponentially (in $n$) but how to use that to confirm that there are no other solutions? – PowerDigitSumGuy Jul 16 '14 at 7:07