Find whether the number of powers of 2, which have a digit sum smaller than , is finite or infinite.
Solution
1. Lemma Statement and Setup:
We need to prove that for a given constant , the set of powers of with a sum of digits not greater than is finite.
Lemma: Write , where the 's are digits. Consider a digit , which is not equal to zero and . Then at least one of is not equal to zero.
2. Proof of Lemma:
Assume to the contrary that the digits are all equal to zero. Write . Now we see that . We also have .
An easy induction shows that and so . Thus , so divides and . But , which is a contradiction. Therefore, our assumption that all digits are zero is false.
3. Application of Lemma:
Now consider a sufficiently large . Since the last digit of is at least , we can start the process of searching for non-zero digits in the expansion of by choosing in the lemma. This gives us a non-zero digit among , and .
We take this non-zero digit and use it again in the lemma. This gives another non-zero digit before . It is evident that by repeating this process, we can find as many non-zero digits as we need.
4. Conclusion:
For some (it is not hard to see that will do the trick), all the powers of after will have a digit sum greater than . Therefore, the number of powers of with a digit sum smaller than is finite.