Finding the number of integers not containing the digit 5

P6.5.4Finding the number of integers not containing the digit 5

Let the column matrix

\mathbf{F_n} = \left( \begin{array}{l}p_n \\ q_n\end{array} \right)

describe the number of non-negative integers less than $$10^n$$ ( $n \ge 0$ ) that do ( $$p_n$$ ) and do not ( $$q_n$$ ) contain the digit 5. Hence, for $$n=1$$ , $$p_1=1$$ and $$q_1=9$$ . Devise a matrix-based recursion relation for finding $\mathbf{F_{n+1}}$ from $\mathbf{F_n}$ .

How many numbers less than $10^{10}$ contain the digit 5?

For each $n \le 10$ , find $$p_n$$ and verify that $$p_n = 10^n - 9^n$$ .

Show solution

The recursion relation is

\mathbf{F_{n+1}} = \mathbf{M}\mathbf{F_n} \;\mathrm{where}\; \mathbf{M} = \left( \begin{array}{rr}10 & 1\\ 0 & 9\end{array} \right).

Life is easier if we start the recursion with

\mathbf{F_0} = \left( \begin{array}{l}0\\1\end{array} \right)

In [x]: M = np.matrix([[10, 1], [0, 9]])
In [x]: F0 = np.matrix([[0], [1]])
In [x]: print(M * F0)   # ie F1
[[1]
 [9]]

To find the number of numbers containing 5 less than $10^{10}$ , simply apply the recursion relation 10 times to $\mathbf{F_0}$ :

In [x]: print(M**10 * F0)
[[6513215599]
 [3486784401]]

That is, there are 6,513,215,599 positive integers less than 10,000,000,000 which contain the digit 5.

For a more direct solution, observe that the number of numbers $$<10^n$$ which do not contain a 5 is $$9^n$$ (since there are 9 ways to choose each digit out of the 10 available, including 0), so there are $$10^n - 9^n$$ numbers which do contain a 5:

In [x]: for n in range(1,11):
   ...:     pn = (M**n * F0)[0]
   ...:     print(pn, pn == 10**n - 9**n)
   ...:
[[1]] [[ True]]
[[19]] [[ True]]
[[271]] [[ True]]
[[3439]] [[ True]]
[[40951]] [[ True]]
[[468559]] [[ True]]
[[5217031]] [[ True]]
[[56953279]] [[ True]]
[[612579511]] [[ True]]
[[6513215599]] [[ True]]