Kvant Math Problem 390

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m01s
Source on kvant.digital

Problem

Prove that there exist infinitely many natural $n$ for which the sum of digits of the number $2^n$ is greater than the sum of digits of the number $2^{n+1}$.

S. V. Konyagin

Moscow Mathematical Olympiad (1976)

Exploration

Let $s(m)$ denote the sum of decimal digits of $m$. The problem asks for infinitely many $n$ such that

$$s(2^n) > s(2^{n+1}) = s(2 \cdot 2^n).$$

Thus we are looking for integers whose digit sum strictly decreases under multiplication by $2$. A decrease of digit sum can only occur when carries in decimal addition create digits $0$ or $1$ in higher positions while eliminating several $9$’s in lower positions. The most effective way for this to happen is when $2^n$ contains a long block of trailing $9$’s, since

$$\underbrace{999\cdots 9}_{k \text{ digits}} \cdot 2 = 1999\cdots 98,$$

and the digit sum drops by $k-1$.

This suggests trying to force arbitrarily long terminal strings of $9$’s in $2^n$, which is equivalent to finding $n$ such that

$$2^n \equiv -1 \pmod{10^k}$$

for arbitrarily large $k$. The difficulty is whether powers of $2$ can land at $-1$ modulo high powers of $5$, since modulo $2^k$ there is no restriction for large $n$.

Thus the key structural question becomes whether $2$ generates the multiplicative group modulo $5^k$, which would allow construction of such exponents systematically.

Problem Understanding

This is a Type B problem. We must prove that there exist infinitely many natural numbers $n$ such that

$$s(2^n) > s(2^{n+1}).$$

The core difficulty is to construct infinitely many powers of $2$ whose decimal expansions end in arbitrarily long strings of $9$’s, because such endings guarantee that doubling decreases the digit sum.

The correct strategy is to show that for every $k$ there exists $n$ such that $2^n \equiv -1 \pmod{10^k}$, and then to verify that this implies $s(2^n) > s(2^{n+1})$.

Proof Architecture

The first lemma establishes that for every positive integer $k$, there exists $n$ such that $2^n \equiv -1 \pmod{5^k}$; this follows from the fact that $2$ is a primitive root modulo $5^k$.

The second lemma lifts this to a congruence modulo $10^k$, showing that the same exponent also forces $2^n \equiv -1 \pmod{10^k}$ because $2^n$ is automatically divisible by $2^k$ for sufficiently large $n$.

The third lemma translates the congruence $2^n \equiv -1 \pmod{10^k}$ into the statement that the last $k$ digits of $2^n$ are all $9$.

The final step shows that such a block of $9$’s forces a strict decrease in digit sum after multiplication by $2$.

The most delicate point is the claim that $2$ is a primitive root modulo $5^k$ for all $k$, since the entire construction depends on this lifting property.

Solution

Fix a positive integer $k$. We begin by studying the multiplicative group modulo $5^k$. The group $(\mathbb{Z}/5^k\mathbb{Z})^\times$ has order $4\cdot 5^{k-1}$. We prove that $2$ is a primitive root modulo $5^k$, meaning its order is exactly $4\cdot 5^{k-1}$.

For $k=1$, modulo $5$, one computes

$$2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 3,\quad 2^4 \equiv 1 \pmod{5},$$

so the order of $2$ modulo $5$ is $4$.

Assume now that $2$ has order $4\cdot 5^{k-1}$ modulo $5^k$. We show that modulo $5^{k+1}$ the order increases by a factor of $5$. Consider

$$2^{4\cdot 5^{k-1}} \equiv 1 + a\cdot 5^k \pmod{5^{k+1}}$$

for some integer $a$ not divisible by $5$. If $a$ were divisible by $5$, then $2^{4\cdot 5^{k-1}} \equiv 1 \pmod{5^{k+1}}$, contradicting maximality of the order modulo $5^k$. Hence the order modulo $5^{k+1}$ is exactly $4\cdot 5^k$. This completes the induction that $2$ is a primitive root modulo $5^k$ for all $k$.

Since $2$ is a primitive root modulo $5^k$, there exists an exponent

$$n_k = \frac{1}{2}\varphi(5^k) = 2\cdot 5^{k-1}$$

such that

$$2^{n_k} \equiv -1 \pmod{5^k}.$$

We now pass to modulus $10^k = 2^k 5^k$. For $k \le n_k$, the number $2^{n_k}$ is divisible by $2^{n_k}$ and in particular by $2^k$, so the congruence modulo $10^k$ is equivalent to the congruence modulo $5^k$ together with sufficient divisibility by $2^k$. Since $n_k \ge k$ for all $k \ge 1$, we obtain

$$2^{n_k} \equiv -1 \pmod{10^k}.$$

The congruence $2^{n_k} \equiv -1 \pmod{10^k}$ means that the last $k$ digits of $2^{n_k}$ form the number $10^k - 1$, namely a block of $k$ digits all equal to $9$.

Let

$$2^{n_k} = A\cdot 10^k + (10^k - 1),$$

where $A$ is a nonnegative integer. Then

$$2^{n_k+1} = 2A\cdot 10^k + (2\cdot 10^k - 2) = (2A+1)\cdot 10^k + (10^k - 2).$$

Thus the last $k$ digits of $2^{n_k+1}$ are obtained by doubling a block of $k$ nines, producing

$$999\cdots 9 \cdot 2 = 1999\cdots 98.$$

The digit sum of the block $999\cdots 9$ equals $9k$. After doubling, the block becomes $1999\cdots 98$, whose digit sum equals $1 + 9(k-2) + 8 = 9k - (k-1)$. Hence the digit sum decreases by $k-1$ in the last $k$ digits, while the higher digits remain unchanged except for a single carry into the $10^k$ place, which does not compensate for this loss. Therefore,

$$s(2^{n_k}) > s(2^{n_k+1}).$$

Since $k$ is arbitrary, the sequence ${n_k}$ is infinite, completing the proof.

∎

Verification of Key Steps

The crucial arithmetic point is the effect of doubling a number ending in $k$ digits all equal to $9$. Writing $10^k - 1$ explicitly, multiplication gives

$$2(10^k - 1) = 2\cdot 10^k - 2 = 10^k + (10^k - 2),$$

which corresponds exactly to a carry of $1$ into the $(k+1)$-st digit and a trailing block $999\cdots 98$. This computation ensures that no further hidden carries arise inside the block, since every position except the last behaves independently under the subtraction of $2$.

The second delicate point is the existence of exponents $n_k$ with $2^{n_k} \equiv -1 \pmod{5^k}$. This depends entirely on the fact that the order of $2$ modulo $5^k$ equals $4\cdot 5^{k-1}$, so that the midpoint of the cyclic group yields $-1$. The base case modulo $5$ and the lifting of order to higher powers of $5$ guarantee this structure without exception.

Finally, the implication from a congruence modulo $10^k$ to a statement about decimal digits is exact, since congruence modulo $10^k$ encodes precisely the last $k$ decimal digits.

Alternative Approaches

A different approach replaces primitive roots with 5-adic analysis, constructing $n$ such that $2^n$ approaches $-1$ in the $5$-adic topology and then translating this into long strings of trailing $9$’s. Another method uses properties of carries in binary exponentiation and density arguments for residue classes of $2^n$ modulo $10^k$. The primitive root argument is preferable because it gives an explicit and uniform construction of the exponents $n_k$ and reduces the problem to a clean structural fact about $(\mathbb{Z}/5^k\mathbb{Z})^\times$.