TAOCP 4.2.4 Exercise 17
Let A_k=\{n\ge 1:(\log_{10} n)\bmod 1<r\}, where $0\le r\le 1$.
Section 4.2.4: Distribution of Floating Point Numbers
Exercise 17. ▶ [HM25] (M. Tsuji.) Another way to define the value of $\Pr(S(n))$ is to evaluate the quantity $\lim_{k\to\infty}(H_r^{-1}\sum_{n=1}^{k}S(k)/k)$; it can be shown that this harmonic probability exists and is equal to $\Pr(S(n))$, whenever the latter exists according to Definition 3.5A. Prove that the harmonic probability of the statement "$(\log_{10} n) \bmod 1 < r$" exists and equals $r$. (Thus, initial digits of integers satisfy the logarithmic law exactly in this sense.)
Verified: yes
Solve time: 1m35s
Solution
Let
$$ A_k={n\ge 1:(\log_{10} n)\bmod 1<r}, $$
where $0\le r\le 1$. We must show that the harmonic probability of $A_r$ exists and is equal to $r$.
By definition, the harmonic probability is
$$ \lim_{N\to\infty}\frac1{H_N}\sum_{n=1}^{N}\frac{\chi_{A_r}(n)}{n}, $$
where
$$ H_N=\sum_{n=1}^{N}\frac1n $$
and $\chi_{A_r}$ is the indicator function of $A_r$.
The condition
$$ (\log_{10} n)\bmod 1<r $$
is equivalent to the existence of an integer $m\ge0$ such that
$$ 10^m\le n<10^{m+r}. $$
Hence
$$ \sum_{n=1}^{N}\frac{\chi_{A_r}(n)}{n} = \sum_{m\ge0} \sum_{\substack{10^m\le n<10^{m+r}\ n\le N}} \frac1n . $$
Let
$$ M=\lfloor\log_{10}N\rfloor, \qquad N=10^{M+t}, \qquad 0\le t<1. $$
For every complete decade $0\le m<M$,
$$ \sum_{10^m\le n<10^{m+r}}\frac1n = \log(10^{m+r})-\log(10^m)+O(10^{-m}), $$
because
$$ \sum_{a\le n<b}\frac1n = \log\frac{b}{a}+O!\left(\frac1a\right). $$
Therefore
$$ \sum_{10^m\le n<10^{m+r}}\frac1n = r\log 10+O(10^{-m}). $$
Summing over $m=0,\ldots,M-1$ gives
$$ \sum_{m=0}^{M-1} \sum_{10^m\le n<10^{m+r}} \frac1n = Mr\log 10+O(1), $$
since
$$ \sum_{m\ge0}10^{-m} $$
converges.
The incomplete final decade contributes at most
$$ \sum_{10^M\le n\le N}\frac1n = O(1), $$
hence
$$ \sum_{n=1}^{N}\frac{\chi_{A_r}(n)}{n} = Mr\log 10+O(1). $$
On the other hand,
$$ H_N=\log N+O(1) =(M+t)\log 10+O(1). $$
Consequently,
$$ \frac1{H_N} \sum_{n=1}^{N}\frac{\chi_{A_r}(n)}{n} = \frac{Mr\log 10+O(1)} {(M+t)\log 10+O(1)}. $$
Since $t$ is bounded and $M\to\infty$ as $N\to\infty$,
$$ \lim_{N\to\infty} \frac{Mr\log 10+O(1)} {(M+t)\log 10+O(1)} = r. $$
Therefore the harmonic probability of the statement
$$ (\log_{10} n)\bmod 1<r $$
exists and is equal to $r$.
Thus the leading digits of the positive integers obey the logarithmic law exactly with respect to harmonic probability.
This completes the proof.
∎