Counting Digits

Starting from zero the natural numbers are written down in base $10$ like this:

$0\,1\,2\,3\,4\,5\,6\,7\,8\,9\,10\,11\,12\cdots$

Consider the digit $d=1$. After we write down each number $n$, we will update the number of ones that have occurred and call this number $f(n,1)$. The first values for $f(n,1)$, then, are as follows:
\begin{array}{cc}
n & f(n, 1)\\
\hline
0 & 0\\
1 & 1\\
2 & 1\\
3 & 1\\
4 & 1\\
5 & 1\\
6 & 1\\
7 & 1\\
8 & 1\\
9 & 1\\
10 & 2\\
11 & 4\\
12 & 5
\end{array}

Note that $f(n,1)$ never equals $3$.

So the first two solutions of the equation $f(n,1)=n$ are $n=0$ and $n=1$. The next solution is $n=199981$.
In the same manner the function $f(n,d)$ gives the total number of digits $d$ that have been written down after the number $n$ has been written.

In fact, for every digit $d \ne 0$, $0$ is the first solution of the equation $f(n,d)=n$.
Let $s(d)$ be the sum of all the solutions for which $f(n,d)=n$.

You are given that $s(1)=22786974071$.
Find $\sum s(d)$ for $1 \le d \le 9$.
Note: if, for some $n$, $f(n,d)=n$ for more than one value of $d$ this value of $n$ is counted again for every value of $d$ for which $f(n,d)=n$.

The first thing we need to note in this problem is that the function $f(n, d)$ gives the total number of times the digit $d$ has been written down after the number $n$ has been written. Therefore, the equation $f(n, d) = n$ gives values of $n$ where the number of times d appears is equal to the value of n itself.

This kind of problem usually needs to be solved using programming or some form of enumeration or brute force algorithm.

In this problem we are also given the sum of these values for $d=1$ as $s(1)$. Without a doubt, calculating the next value of $n$ that will satisfy the equation $f(n, d) = n$ is a monotonous task and requires enumeration since we need to check the number of times each digit d occurs after each n.

However, the key insight is that $f(n, d)$ increases much slowly as $n$ increases, hence the solutions $n$ for $f(n, d) = n$ would be huge values and there would be very few of these solutions. This is clear from the fact that for the digit $d = 1$ the third solution is $n = 199981$.

When we are required to find $\sum s(d)$ for $1 \leq d \leq 9$, we are summing up the $s(d)$ for each digit $d$. However, as we noted earlier, solutions for $f(n, d) = n$ are few and very large hence it is likely that the solutions don’t overlap for different values of d, as it is highly unlikely for these large numbers to satisfy $f(n, d) = n$ for different values of d.

This greatly simplifies the problem, because we can assume that all solutions are unique across different d. Therefore, the sum of $s(d)$ would be the same $s(d)$ value for all $d$, since every digit appears the same number of times overall.

Hence, $\sum_{1 \leq d \leq 9} s(d) = 9 \cdot s(1) = 9 \cdot 22786974071 = 205082766639$.

Please note that this proof is heuristic and based on the likelihood of events. It does not provide a rigorous mathematical proof for this problem. This problem was originally a Project Euler problem, which is a series of challenging mathematical/computer programming problems that require more than just mathematical insights to solve.

More Answers: