Maths Olympiad Prep

Library / /94 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Find whether the number of powers of 2, which have a digit sum smaller than 201920192019^{2019}, is finite or infinite.

Solution

1. Lemma Statement and Setup:
We need to prove that for a given constant λ\lambda, the set of powers of 22 with a sum of digits not greater than λ\lambda is finite.

Lemma: Write 2n=cmcm1c2c12^n = \overline{c_{m}c_{m-1} \cdots c_2c_1}, where the cic_i's are digits. Consider a digit ckc_k, which is not equal to zero and 4km4k \leq m. Then at least one of {ck+1,ck+2,,c4k}\{c_{k+1}, c_{k+2}, \cdots, c_{4k}\} is not equal to zero.

2. Proof of Lemma:
Assume to the contrary that the digits ck+1,ck+2,,c4kc_{k+1}, c_{k+2}, \cdots, c_{4k} are all equal to zero. Write t=ckck1c1t = \overline{c_kc_{k-1} \cdots c_1}. Now we see that t<10kt < 10^k. We also have 2nt(mod104k)2^n \equiv t \pmod{10^{4k}}.

An easy induction shows that nmn \geq m and so n4kn \geq 4k. Thus t2n0(mod24k)t \equiv 2^n \equiv 0 \pmod{2^{4k}}, so 24k2^{4k} divides tt and t16kt \geq 16^k. But t<10k<16kt < 10^k < 16^k, which is a contradiction. Therefore, our assumption that all digits ck+1,ck+2,,c4kc_{k+1}, c_{k+2}, \cdots, c_{4k} are zero is false.

3. Application of Lemma:
Now consider a sufficiently large NN. Since the last digit of 2N2^N is at least 22, we can start the process of searching for non-zero digits in the expansion of 2N2^N by choosing k=1k=1 in the lemma. This gives us a non-zero digit among c2,c3c_2, c_3, and c4c_4.

We take this non-zero digit and use it again in the lemma. This gives another non-zero digit before c17c_{17}. It is evident that by repeating this process, we can find as many non-zero digits as we need.

4. Conclusion:
For some NN (it is not hard to see that N4λ1N \geq 4^{\lambda-1} will do the trick), all the powers of 22 after 2N2^N will have a digit sum greater than λ\lambda. Therefore, the number of powers of 22 with a digit sum smaller than 201920192019^{2019} is finite.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.