Problem: Let \(f(n)\) = the number of zeros in the decimal representation of \(n\). For example, \(f(1009)=2\). For \(a>0\), define

\(S(N)=\displaystyle\sum_{k=1}^{N}a^{f(k)}\).

Evaluate

\(L=\displaystyle\lim_{N\to\infty}\frac{\log S(N)}{\log N}\).

Solution: The key is to recognize that the sum \(S(N)\) is best evaluated according to how many digits are in \(N\). As an example, suppose \(N=9\): none of the single-digit numbers between 1 and 9 have zeros, so the sum \(S(N)\) is equal to 9. Within the two-digit numbers, note that there are 9 numbers with 1 zero [e.g., 10, 20,…,90] and the rest [90-9=81] with no zeros; in this case \(S(99)=9 a+81+S(9)=9 a+9^2+S(9)\). For three-digit numbers, there are 3 possibilities: the number can have 2, 1, or no zeros. There are 9 such numbers with two zeros. Numbers with 1 zero include 101 and 110; note that there are 2 different numbers resulting from two non-zero digits and one zero digit. Given that there are \(9^2\) combinations of digits, it is clear that there are \(2\times 9^2\) three-digit numbers having exactly one zero digit. Finally, there are \(900-162-9=729=9^3\) three-digit numbers with no zeros. Therefore,

\(S(999)=S(10^3-1)=9 a^2+2\times 9^2 a+9^3+S(10^2-1)\).

The pattern here is clear to the [mathematically inclined] observer:

\(S(10^k-1)=9 a^{k-1}+\binom{k-1}{1}\times 9^2 a^{k-2}+\ldots+\binom{k-1}{k-2}\times 9^{k-1} a+9^{k}+S(10^{k-1}-1)\)or

\(S(10^k-1)=9 (a+9)^{k-1}+S(10^{k-1}-1)=9 \displaystyle\sum_{j=0}^{k-1} (a+9)^{j}\).

Summing the series, we arrive at the following:

\(S(10^k-1)=9 \frac{(a+9)^{k}-1}{a+8}\).

In evaluating \(L\), observe that the limit \(N\to\infty\) is equivalent to \(k\to\infty\). In this limit, \(\log N \approx k\). We therefore get the final result:

\(L=\log (a+9)\)