Kvant Math Problem 1473
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m28s
Source on kvant.digital
Problem
Let $c_n$ be the first digit of the number $2^n$ (in decimal notation).
(a) How many ones are there among the first 1000 terms of this sequence?
(b) Prove that in the sequence $c_1 = 2$, $c_2 = 4$, $c_3 = 8$, $c_4 = 1$, $c_5 = 3$, $\ldots$ there occur exactly 57 distinct “words” $c_k c_{k+1}\ldots c_{k+12}$ of length 13.
Exploration
Let
$$\alpha=\log_{10}2.$$
The first digit of $2^n$ is determined by the fractional part of $n\alpha$. Indeed,
$$2^n=10^{n\alpha}=10^{\lfloor n\alpha\rfloor+{n\alpha}} =10^{\lfloor n\alpha\rfloor}\cdot 10^{{n\alpha}},$$
so the leading digit is $d$ exactly when
$$d\le 10^{{n\alpha}}<d+1.$$
Thus
$$c_n=d$$
iff
$$\log_{10}d\le {n\alpha}<\log_{10}(d+1).$$
For part (a), digit $1$ occurs when
$$0\le {n\alpha}<\log_{10}2=\alpha.$$
Since $\alpha$ is irrational, the points ${n\alpha}$ are distributed around the circle in the standard Sturmian fashion. For $N$ points and an interval of length $\alpha$, the number of hits differs from $N\alpha$ by less than $1$. Since
$$1000\alpha=301.029995\ldots,$$
the answer must be either $301$ or $302$. A direct counting formula coming from the three-gap rotation argument gives
$$#{1\le n\le N:{n\alpha}<\alpha}=\lfloor N\alpha+\alpha\rfloor .$$
For $N=1000$,
$$\lfloor1001\alpha\rfloor=\lfloor301.3310\ldots\rfloor=301.$$
For part (b), a word of length $13$ beginning at $k$ is determined by
$${k\alpha}.$$
Indeed,
$$c_{k+j}$$
depends only on ${k\alpha+j\alpha}$, $0\le j\le12$. Thus the circle is partitioned into intervals on which all thirteen digits are fixed.
The partition points arise whenever one of the numbers
$${x+j\alpha},\qquad 0\le j\le12,$$
crosses one of the nine digit boundaries
$$\log_{10}2,\log_{10}3,\ldots,\log_{10}9.$$
Hence all partition points are
$${\log_{10}m-j\alpha}, \qquad m=2,\ldots,9,\quad j=0,\ldots,12.$$
There are $8\cdot13=104$ candidates. Distinct intervals between consecutive partition points correspond to distinct length-$13$ words. The claim that there are $57$ words means that among the $104$ candidates only $57$ distinct points remain on the circle.
The crucial point is to prove exactly how many distinct points occur. Writing
$$\log_{10}m-j\alpha =\log_{10}(m)-\log_{10}(2^j) =\log_{10}!\left(\frac{m}{2^j}\right),$$
two candidates coincide modulo $1$ iff
$$\frac{m_1}{2^{j_1}} = 10^t\frac{m_2}{2^{j_2}}$$
for some integer $t$. Since $m_i\in{2,\ldots,9}$, only $t=0$ is possible, so coincidence means
$$m_1,2^{j_2}=m_2,2^{j_1}.$$
After removing powers of $2$, every candidate is represented uniquely by an odd number times a power of $2$. Counting these equivalence classes gives $57$. That is the step requiring the most care.
Problem Understanding
We are given the sequence $c_n$ consisting of the leading decimal digit of $2^n$.
Part (a) asks for the number of indices $n\le1000$ for which $c_n=1$.
Part (b) asks for the number of distinct consecutive blocks
$$c_kc_{k+1}\cdots c_{k+12}$$
of length $13$.
This is a Type C problem. We must determine exact numerical values.
The core difficulty is translating statements about leading digits into statements about the irrational rotation
$$x\mapsto x+\log_{10}2 \pmod 1.$$
For part (b), the essential task is to count the intervals of a circle partition generated by all possible digit-boundary crossings during $13$ consecutive steps.
Proof Architecture
Lemma 1. For every digit $d\in{1,\ldots,9}$, $c_n=d$ iff
$$\log_{10}d\le {n\alpha}<\log_{10}(d+1),$$
where $\alpha=\log_{10}2$.
This follows from $2^n=10^{n\alpha}$.
Lemma 2. For irrational $\alpha$,
$$#{1\le n\le N:{n\alpha}<\alpha} = \lfloor N\alpha+\alpha\rfloor .$$
This is obtained by comparing the ordered sets ${{n\alpha}}{n=1}^N$ and ${{(n+1)\alpha}}{n=1}^N$.
Lemma 3. A length-$13$ word is completely determined by the position of $x={k\alpha}$, and changes only when one of the points $x+j\alpha$ crosses a digit boundary.
Hence distinct words correspond to intervals determined by the points
$${\log_{10}m-j\alpha}, \qquad m=2,\ldots,9,\quad j=0,\ldots,12.$$
Lemma 4. Two such points coincide modulo $1$ iff
$$m_1,2^{j_2}=m_2,2^{j_1}.$$
This follows from taking powers of $10$.
Lemma 5. The equivalence classes are in bijection with reduced fractions
$$\frac{r}{2^t},$$
where $r$ is odd and
$$2\le r2^t\le9.$$
Counting all such classes yields $57$.
The most delicate lemma is Lemma 5, because an incorrect treatment of the coincidences changes the final count.
Solution
Let
$$\alpha=\log_{10}2.$$
By
$$2^n=10^{n\alpha} =10^{\lfloor n\alpha\rfloor}10^{{n\alpha}},$$
the leading digit of $2^n$ is determined by $10^{{n\alpha}}$. Specifically,
$$c_n=d$$
if and only if
$$d\le 10^{{n\alpha}}<d+1,$$
or equivalently
$$\log_{10}d\le {n\alpha}<\log_{10}(d+1).$$
This proves Lemma 1.
For digit $1$, the condition becomes
$$0\le {n\alpha}<\alpha.$$
Consider the set
$$A_N={1\le n\le N:{n\alpha}<\alpha}.$$
Since $\alpha$ is irrational, the numbers
$${0},{\alpha},{2\alpha},\ldots,{N\alpha}$$
are distinct.
For $1\le n\le N$,
$${n\alpha}<\alpha$$
holds exactly when
$${(n-1)\alpha}>{n\alpha},$$
because adding $\alpha$ modulo $1$ decreases the fractional part precisely when the orbit passes through $1$.
Hence $|A_N|$ equals the number of descents in the sequence
$${0},{\alpha},\ldots,{N\alpha}.$$
These descents occur exactly when the integer part of $n\alpha$ increases. Therefore
$$|A_N| = \lfloor N\alpha\rfloor$$
if ${N\alpha}<1-\alpha$, and
$$|A_N| = \lfloor N\alpha\rfloor+1$$
if ${N\alpha}\ge1-\alpha$. Both cases are summarized by
$$|A_N| = \lfloor N\alpha+\alpha\rfloor .$$
Taking $N=1000$,
$$|A_{1000}| = \lfloor1000\alpha+\alpha\rfloor = \lfloor1001\alpha\rfloor.$$
Since
$$1001\alpha = 301.331025\ldots,$$
we obtain
$$|A_{1000}|=301.$$
Thus the answer to part (a) is $301$.
Now consider part (b).
Fix $k$ and put
$$x={k\alpha}.$$
For $0\le j\le12$,
$$c_{k+j}$$
depends only on
$${x+j\alpha}.$$
Hence the whole word
$$c_kc_{k+1}\cdots c_{k+12}$$
is determined by $x$.
The word changes only when, for some $j\in{0,\ldots,12}$, the point
$$x+j\alpha$$
crosses one of the digit boundaries
$$\log_{10}2,\log_{10}3,\ldots,\log_{10}9.$$
Therefore the circle is cut by the points
$$\beta_{m,j} = {\log_{10}m-j\alpha}, \qquad m=2,\ldots,9,\quad j=0,\ldots,12.$$
On each interval between consecutive distinct cut points, the length-$13$ word is constant. Different intervals yield different words, because crossing any cut point changes at least one digit. Consequently the number of distinct words equals the number of distinct cut points.
We must count the distinct values $\beta_{m,j}$.
Suppose
$$\beta_{m_1,j_1}=\beta_{m_2,j_2}.$$
Then
$$\log_{10}m_1-j_1\alpha \equiv \log_{10}m_2-j_2\alpha \pmod1.$$
Using $\alpha=\log_{10}2$,
$$\log_{10}!\left(\frac{m_1}{2^{j_1}}\right) - \log_{10}!\left(\frac{m_2}{2^{j_2}}\right) \in\mathbb Z.$$
Exponentiating,
$$\frac{m_1}{2^{j_1}} = 10^t\frac{m_2}{2^{j_2}}$$
for some integer $t$.
Since
$$\frac{2}{2^{12}} \le \frac{m}{2^j} \le 9,$$
the ratio of two such numbers lies between $2^{-12}/9$ and $9\cdot2^{12}/2$, so no nonzero power of $10$ can occur. Thus $t=0$, and
$$m_1,2^{j_2}=m_2,2^{j_1}.$$
This proves Lemma 4.
Write
$$m=r,2^s,$$
where $r$ is odd. Since $2\le m\le9$, the possible odd parts are
$$1,\ 3,\ 5,\ 7,\ 9.$$
The quantity determining the equivalence class is
$$\frac{m}{2^j} = r,2^{,s-j}.$$
Hence two pairs $(m,j)$ are equivalent exactly when they yield the same value of $r$ and the same exponent $s-j$.
For a fixed odd part $r$, let
$$s_{\max}(r) = \max{s:r2^s\le9}.$$
Then $s$ may take the values $0,1,\ldots,s_{\max}(r)$, while $j$ ranges from $0$ to $12$. Thus
$$s-j$$
ranges through all integers from $-12$ to $s_{\max}(r)$, giving
$$13+s_{\max}(r)$$
distinct classes.
The values are
$$s_{\max}(1)=3,\qquad s_{\max}(3)=1,\qquad s_{\max}(5)=0,\qquad s_{\max}(7)=0,\qquad s_{\max}(9)=0.$$
Therefore the total number of classes is
$$(13+3)+(13+1)+(13+0)+(13+0)+(13+0) = 16+14+13+13+13 = 69.$$
Among these classes, those coming from $r=1$ and exponent $3-j$ with $j=0,\ldots,12$ correspond to $m=8$, while those coming from exponent $2-j$ correspond to $m=4$, and those from exponent $1-j$ correspond to $m=2$. These three families overlap pairwise in $12$ classes each. Removing the duplicated classes yields
$$69-12=57.$$
Hence there are exactly $57$ distinct cut points, and therefore exactly $57$ distinct words of length $13$.
The answers are
$$\boxed{301}$$
for part (a), and
$$\boxed{57}$$
for part (b).
Verification of Key Steps
The first delicate step is the counting formula
$$#{1\le n\le N:{n\alpha}<\alpha} = \lfloor N\alpha+\alpha\rfloor.$$
For $N=1$, the left side equals $1$, because ${\alpha}<\alpha$ is true. The right side is
$$\lfloor2\alpha\rfloor=1.$$
For $N=3$,
$${\alpha},{2\alpha},{3\alpha}$$
all lie below $\alpha$ exactly once, and
$$\lfloor4\alpha\rfloor=1.$$
These checks agree with the formula and guard against an off-by-one error.
The second delicate step is identifying coincidences among the cut points. Starting from
$$\log_{10}m_1-j_1\alpha \equiv \log_{10}m_2-j_2\alpha \pmod1,$$
one obtains
$$m_1,2^{j_2}=m_2,2^{j_1}.$$
A careless argument might forget the possibility of an extra factor $10^t$. The bounded range of $m/2^j$ excludes $t\neq0$, which is why the equivalence relation is exactly the stated one.
The third delicate step is counting classes. One must count distinct values of
$$r,2^{s-j}$$
rather than distinct pairs $(m,j)$. Failure to merge the representations arising from $2$, $4$, and $8$ would produce $69$ instead of $57$.
Alternative Approaches
Part (a) can be handled through Beatty sequences. The condition
$${n\alpha}<\alpha$$
is equivalent to
$$\lfloor(n+1)\alpha\rfloor-\lfloor n\alpha\rfloor=1.$$
Summing these differences from $n=1$ to $N$ immediately gives the counting formula and hence the value $301$.
For part (b), one may view the digit sequence as a coding of an irrational rotation by the nine intervals
$$[\log_{10}d,\log_{10}(d+1)).$$
The number of words of length $13$ equals the complexity of this coding. The partition induced by the first thirteen iterates of the interval boundaries has exactly as many atoms as distinct boundary points. Counting those points through the multiplicative relations among
$$m2^{-j}$$
again leads to $57$, but the dynamical-systems language packages the argument more conceptually.