# How to count each numeral of occurrences of digits?

I want to count each numeral(0 through 9) of occurrences of digits in the range $[1, n]$. Note that 101 has two one and one zero.

For example, if $n$ equals $11$:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline f_0(11) & f_1(11) & f_2(11) & f_3(11) & f_4(11) & f_5(11) & f_6(11) & f_7(11) & f_8(11) & f_9(11)\\ \hline 1 & 4 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline \end{array}

How can I generalize about this function to $f$?

• There are 4 $1$s in $11?$ Who knew? Commented Apr 10, 2015 at 10:46
• what do you mean to generalize this to $f$? What is $f$? Do you want a function $f: Z^+ \to (Z^+)^{10}$ which outputs all of the numbers at once? Commented Apr 10, 2015 at 10:47
• Ah, it is the number of $1$s in $1,2,3,4,5,6,7,8,9,10,11$. So it is the sum of the number of occurrences. Commented Apr 10, 2015 at 10:50

Let us take a first step. I think $f_0$ will be more tricky, but some easy figures are $f_i(10^k-1)$ for $i\geq 1$. This corresponds to aksing how many occurrences there are of the digit $i$ in the $10^k$ possible $k$-digit strings $$0...0,0...1,...,9...9$$ and since all $10$ digits by symmetry occur equally often in those strings, the digit $i$ must have occurred exactly $$\frac1{10}\cdot k\cdot 10^k=k\cdot 10^{k-1}\text{ times}$$ Thus $f_i(9)=1,f_i(99)=20,f_i(999)=300$ and so on.

Based on the above, we can describe $f_i(10^ka)$ where $a$ is a non-zero digit. We have $$f_i(10^ka)= \begin{cases} a\cdot f_i(10^k-1)&=ak\cdot 10^{k-1}&\text{for }a<i\\ a\cdot f_i(10^k-1)+1&=ak\cdot 10^{k-1}+1&\text{for }a=i\\ a\cdot f_i(10^k-1)+10^k&=(ak+10)\cdot10^{k-1}&\text{for }a>i \end{cases}$$ note that $f_i(10^k-1)$ counts the number of occurrences of $i$ in the last $k$ digits, whereas the $+1$ and $+10^k$ adds the number of times $i$ occurs in the first digit.

Now to the general case of $f_i(10^ka+b)$ where $a$ is a non-zero digit and $b$ is some number with at most $k$ digits. Here we have $$f_i(10^ka+b)= \begin{cases} f_i(10^ka)+f_i(b)&\text{for }a\neq i\\ f_i(10^ka)+f_i(b)+b&\text{for }a=i \end{cases}$$ and applying the formulas for $f_i(10^ka)$ from before, this gives us $$f_i(10^ka+b)= \begin{cases} ak\cdot 10^{k-1}+f_i(b)&\text{for }a<i\\ ak\cdot 10^{k-1}+1+f_i(b)+b&\text{for }a=i\\ (ak+10)\cdot 10^{k-1}+f_i(b)&\text{for }a>i\\ \end{cases}$$

For a given number $n=10^ka+b$, those formulas can be applied recursively for each non-zero digit $i\geq 1$. Thus we can determine $f_1(n),f_2(n),...,f_9(n)$. There will be $(a-1)\cdot10^k$ and $(b+1)$ numbers having $(k+1)$ digits and $9\cdot 10^{s-1}$ having $s$ digits for each $s<k+1$. Thus our numbers have a total of $$T(n)=(k+1)\left[b+1+(a-1)\cdot 10^k\right]+\sum_{s=1}^k 9s\cdot 10^{s-1}\text{ digits}$$ and from this $f_0(n)$ can be computed as $$f_0(n)=T(n)-\sum_{i=1}^9 f_i(n)$$

## Examples

As an example, consider $n=123$. Then \begin{align} f_2(123)&=1\cdot2\cdot10^1+f_2(23)\\ &=20+2\cdot 1\cdot 10^0+1+f_2(3)+3\\ &=20+2+1+1+3\\ &=27 \end{align} noting that $f_2(3)=1$. This is easily checked to be correct. I wrote a few lines of code scanning through $1,2,...,123$ as strings counting occurrences of "2". It confirmed the figure $27$.

One more example, let us try $n=314159$ and $i=3$: \begin{align} f_3(314159)&=3\cdot5\cdot 10^4+1+f_3(14159)+14159\\ &=164160+1\cdot 4\cdot 10^3+f_3(4159)\\ &=168160+(4\cdot 3+10)\cdot 10^2+f_3(159)\\ &=170360+1\cdot 2\cdot 10^1+f_3(59)\\ &=170380+(5\cdot 1+10)\cdot 10^0+f_3(9)\\ &=170396 \end{align} and again my computer confirmed this figure.

• BTW: I think that my recursion runs in something like $O(\log n)$ whereas a simple scan runs in $O(n\log n)$ if I am not mistaken. I have not thought too deeply about that, though. At least I can actually see, how the performance is unequal using the two different methods. The recursion computes large figures almost instantly whereas the scan gets remarkably slower for large $n$'s. Commented Apr 11, 2015 at 0:14