# How many positive integers $< 1{,}000{,}000$ contain the digit $2$?

How many positive integers less than $1{,}000{,}000$ have the digit $2$ in them?

I could determine it by summing it in terms of the number of decimal places, i.e. between $999{,}999$ and $100{,}000$, etc.

Then to determine the number of numbers between $999{,}999$ and $100{,}000$ that have the digit $2$ in them would be $9^5$.

Is this correct, or am I miscounting?

• There are an infinite number of numbers less than 1 with the digit 2 in them, let alone less than 1,000,000. For instance 0.2, 0.22, 0.222, etc. Perhaps you mean how many integers less than 1,000,000 have the digit 2 in their decimal representation? Feb 9, 2014 at 23:39
• Do you mean integers > 0? Feb 9, 2014 at 23:59
• Answer confirmed to be 468559. ideone.com/fb5173 Feb 10, 2014 at 0:04
• There are infinite negative integers that have the digit 2 too Feb 10, 2014 at 0:58
• python: reduce(lambda x,y:x+y, [1 for x in xrange(1000000) if '2' in str(x)])
– user127536
Feb 10, 2014 at 2:19

Though not always the smartest way, such questions can mechanically be answered as follows. (In this case the "smart" way to do it is Cameron's answer. It is instructive to see that this mechanical procedure basically recovers Cameron's method.) Let $a_n$ and $b_n$ be the amounts of $n$-digit numbers that do not and do have a $2$ in them. So $a_0=1$ and $b_0=0$. These number satisfy the recurrence $$\begin{pmatrix}a_{n+1}\\b_{n+1}\end{pmatrix}= \begin{pmatrix}9&0\\1&10\end{pmatrix} \begin{pmatrix}a_n\\b_n\end{pmatrix}$$

(Take a moment to understand what this recurrence expresses.) Now $$\begin{pmatrix}9&0\\1&10\end{pmatrix}^6 \begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}531441\\468559\end{pmatrix}$$

so the answer is $468559=10^6-9^6$.

• +1: I like it! One thing that might be worth addressing is what exactly a zero-digit number is. My first thought would be 0, but that count also seems to include 0 in the one-digit numbers. Perhaps it would be simpler to begin with $a_1=9$, $b_1=1$? Feb 9, 2014 at 19:19
• @CameronBuie Think of $0$-digit numbers as empty sequences. There is only one empty sequence and it does not contain the digit $2$. Starting at $n=1$ may be a good idea anyway.
– WimC
Feb 9, 2014 at 20:45
• can you give me one reference where I can learn this kind of things? (counting+recurrences) Feb 14, 2014 at 17:28
• @Vicfred In my case it was learning by doing. I thought that such techniques were called "dynamic programming" but looking at the wp page it's not a great reference. Instead you can try your hand on some project Euler problems although some can be quite hard to crack. This problem is a rather fiendish example. I answered some other questions on mse in the same spirit but have to look them up...
– WimC
Feb 14, 2014 at 18:32
• @WinMc yeah, I take part in codeforces and topcoder that's why I'm trying to improve my dynamic programming skills with problems like this so I'm looking where can I learn. Feb 14, 2014 at 19:03

The number of numbers from $1$ t0 $10^6$ that do not have the digit $2$ is clearly the same as the number of numbers that do not have the digit $9$. Now read each of these in base $9$ and you get all the numbers from 1 to $10^6$ (base 9) $=9^6$ (base 10). Therefore, there are $10^6-9^6$ numbers between $1$ and $10^6$ that use the digit 2.

• Mucking around with unusual number bases normally does my head in, but this seems to be a straight forward method for this problem. Just remember that counting to 1,000,000 in base 9 results in all permutations of symbols 0-8 in all positions in the number. Also each position in the number is a power of 9 so the 1 in the 6th position is 1 * 9^6 just as in base 10 where a 1 in the 6th position is 1 * 10^6 Feb 9, 2014 at 21:35

I'm afraid you've miscounted. In this case, it would be better to count indirectly, by finding the numbers that don't have the digit $2$ in them, then subtracting these from the total.

First, let's count the number of $6$-digit numbers without a $2$ in them. There are $8$ choices for the leading digit of such a number, and for each of the other $5$ digits, there are $9$ choices. Thus, there are $8\cdot 9^5$ such numbers. Similarly, we can find that $8\cdot 9^4$ $5$-digit numbers without a $2$ in them, and so on, down to the $2$-digit numbers. Depending on whether $0$ is considered a $1$-digit number, there are either $8$ or $9$ numbers with one digit and no $2$'s. It turns out that the answer is not affected, either way, as I will discuss below.

Note Depending on whether you are taking $0$ to be a number, the number in the $1$-digit case will differ (though the answer, itself, will not). In fact, if you are taking $0$ to be a number, then the answer is greatly simplified, as you need only choose one of the $9$ available digits for each of the $6$ decimal places. This yields $9^6$ numbers less than $1000000$ without $2$ as a digit, out of a total of $1000000=10^6$ numbers less than $1000000.$ This also suggests an alternate approach in the case that $0$ is not a number being considered. Proceed as before, but discard zero as an option, so there are $9^6-1$ numbers less than $1000000$ without $2$ as a digit, out of a total of $999999=10^6-1$ numbers less than $1000000.$ In either case, there are $10^6-9^6$ numbers less than $1000000$ with $2$ as a digit.

This even agrees with the (more intuitive but less efficient) method outlined above. In general, we can find the sum using the formula for sums of geometric progressions. Alternately, here's a neat trick we can use.

Now, assume that $0$ is not among the numbers under consideration. (As we saw above, this won't make a difference.) In that case, there are $8=8\cdot 9^0$ single-digit numbers not equal to $2$. Hence, there are $$8\cdot9^5+8\cdot9^4+8\cdot9^3+8\cdot9^2+8\cdot9^1+8\cdot9^0$$ numbers less than $1000000$ that do not have $2$ as a digit. Let's call this sum $S$. Now, \begin{align}9S &= 9\left(8\cdot9^5+8\cdot9^4+ 8\cdot9^3+8\cdot9^2+8\cdot9^1+8\cdot9^0\right)\\ &= 8\cdot9^6+8\cdot9^5+8\cdot9^4+8\cdot9^3+8\cdot9^2+8\cdot9^1\\ &= 8\cdot9^6+S-8\cdot9^0\\ &= S+8\cdot\left(9^6-9^0\right)\end{align} so $$8S=8\cdot\left(9^6-9^0\right),$$ and so $$S=9^6-9^0=9^6-1.$$ Since there are $10^6-1$ numbers less than $1000000,$ then as above, there are $$10^6-9^6=468559$$ numbers less than $1000000$ with $2$ as a digit.

• Why make the distinction between numbers of different length? Just fill them up with zeros up to length 6. That will make it even easier.
– bodo
Feb 9, 2014 at 17:19
• @canaaerus: Largely, I took the initial approach because I was unsure whether $0$ would be considered as a number in this case. I have added to my answer to suggest how the simpler approach may be incorporated in either case. Feb 9, 2014 at 17:25
• @muntoo: There is nothing to account for, it’s just a different way of writing the numbers, which makes the counting in this case a lot easier.
– bodo
Feb 9, 2014 at 21:13
• This answer is incorrect. You are skipping all of the valid numbers between 0-99,999 because you are assuming the leading number has to be at least 1, when it can be a zero. For example, the number 37 = 000,037 and is just as valid a number as any other. Just because we do not normally write it with the leading zeroes for base 10 numbers, does not make it invalid or incorrect to do so. This means 9 possible symbols in every position in the number. Making the answer 10^6 - 9^6 Feb 9, 2014 at 21:45
• @BeowulfNode42. If you'll check the edit of the question that was current approximately an hour before your comment (as well as the current edit, which is better), you'll see that all those numbers ($37$ included) are covered. Were they not covered, I would not have found the same answer (as I did). Feb 9, 2014 at 22:07

You can get a generalised answer to this question (assuming that you are always asking how many integers with the digit 2 less than a particular power of 10).

For 10, there is 1
For 100, there is 1 + 1 + 10 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9x1 + 10 = 19
For 1000, there is 19 + 19 + 100 + 19 + 19 + 19 + 19 + 19 + 19 + 19 = 9x19 + 100 = 271


So, to generalise if n is the power of 10,

$$A_1 = 1$$

$$A_n = 10^{n-1}+9A_{n-1}$$

So for 1,000,000,

$$A_6=10^5+9A_5$$ $$A_6=10^5+9(10^4 + 9A_4)$$ $$A_6=10^5+9*10^4+81*A_4$$ $$A_6=10^5+9*10^4+81(10^3+9A_3)$$ $$A_6=10^5+9*10^4+81*10^3+729A_3$$ $$A_6=10^5+9*10^4+81*10^3+729(10^2+9A_2)$$ $$A_6=10^5+9*10^4+81*10^3+729*10^2+6561A_2$$ $$A_6=10^5+9*10^4+81*10^3+729*10^2+6561(10+9A_1)$$ $$A_6=100000+90000+81000+72900+65610+59049$$ $$A_6=468559$$

• most intuitive for me Feb 10, 2014 at 7:03
• @zinking: It's worth noting that this is exactly WimC's approach, in less compact form. Feb 10, 2014 at 13:01
• @CameronBuie getting it now, that's better, but the first pass I didn't get it, how dumb. Feb 10, 2014 at 15:05
• ideone.com/AcV9PR refer this if you want calculations Feb 10, 2014 at 15:06
• I see Pascal's Triangle on that bottom equation reduction. I need to take a break from math... Feb 10, 2014 at 16:55

You are miscounting, the answer is 468,559.

There are 6 digits, each digit can be 0-9. That makes ten options so 10^6 permutations. If you remove 2 from 0-9, there are 9 options so 9^6 permutations.

Set size                   = 10^6 = 1,000,000
Numbers with no 2s         =  9^6 =   531,441
Number with at least one 2 = 10^6 - 9^6
= 1,000,000 - 531,441
= 468,559

• +1 – In my opinion the cleanest and simplest way to arrive at the answer. No separate consideration of numbers of different length, no matrices, no base 9, no recursive formulas. You might want to point out though that for the answer it doesn't matter whether numbers are written with leading zeros. And I think "chance" is misleading, it's just about options (combinatorics, not probability theory); and they are not permutations but combinations. Feb 10, 2014 at 19:30
• @A.Donda You are right, chance is misleading. I originally thought to use probability but quickly realized that permutations could be used directly. I forgot to rephrase that part. Feb 11, 2014 at 2:57

You can easily check your answer with a computer program or by counting.

Split into disjoint cases. There are 6 digits, so the number of numbers with a 2 in k positions and no other positions is $\binom{6}{k} 9^{6-k}$ where the $\binom{6}{k}$ counts the number of ways to choose the k positions of $2$'s and $9^{6-k}$ counts the number of ways to fill the rest of the positions with $\{0,1,3,4,5,6,7,8,9\}$. Summing from $k=1$ to $k=6$ gives you the answer as $\sum_{k=1}^6 \binom{6}{k} 9^{6-k}$.

Alternatively, count the number of numbers which don't have 2's in them. You can choose the 6 digits from $\{0,1,3,4,5,6,7,8,9\}$, so there are $9^6$ such numbers (including $000000=0$). Subtract this from the total number of numbers less than $1,000,000$ and you get your answer as well.

I guess from the group the question was posted in, that you are interested in a more mathematical approach. This is not like that!

It is a very simple condition for a small range and so a modern scripting language makes it easy to compute. Here's the python:

>>> sum(1 for x in range(1000000) if '2' in str(x))
468559
>>>

• +1 BUT, not necessarily an answer per se as it doesn't show the mathematics behind the answer (especially because this is a brute force effort) Feb 10, 2014 at 17:00

This question was linked to Count occurrences of an integer and a possible solution out there would also work for this problem.

$$\text{Let }N= a_na_{n-1}...a_{2}a_{1}a_{0}$$ $$Count(N, K) = \begin{cases} \begin{cases} a_n\left(10^{n-1} - 9^{n-1}\right) & a_n < K \\ \left(a_n-1\right)\left(10^{n-1} - 9^{n-1}\right)+10^{n-1}& a_n > K \\ a_n\left(10^{n-1} - 9^{n-1}\right)+1& a_n = K\end{cases} & a_{n-1}...a_{2}a_{1}a_{0} = 0\\ \begin{cases}Count(a_n0....000) + Count(a_{n-1}...a_{2}a_{1}a_{0})& a_n \ne K \\ Count(a_n0....000) + N \mod 10^{n-1}& a_n = K\end{cases} & a_{n-1}...a_{2}a_{1}a_{0} \ne 0\end{cases}$$

And to extend it to arbitrary range (both inclusive) $$Count(M,N,K)=Count(N,K) - Count(M-1,K)$$

So replacing N=$1,000,000$ and $K=2$, we get

$$Count(0,1000000,2) = Count(1000000,2) = a_n\left(10^{n-1} - 9^{n-1} \right) =\left(10^{6}-9^{6}\right)=468559$$

You can also solve this problem with inclusion exclusion. Let $T_i$ be the set of numbers with a Two in the $i^{th}$ position.

$$S = \vert T_0 \cup T_1 \dots \cup T_5 \vert$$

By inclusion exclusion, this is equal to:

\begin{align} S &= \vert T_0 \vert + \vert T_1 \vert + \dots + \vert T_5 \vert \\ &- \vert T_0 \cap T_1 \vert - \vert T_0 \cap T_2 \vert - \vert T_1 \cap T_2 \vert - \dots - \vert T_4 \cap T_5\vert \\ &+ \vert T_0 \cap T_1 \cap T_2 \vert + \vert T_0 \cap T_1 \cap T_3 \vert + \dots + \vert T_3 \cap T_4 \cap T_5 \vert \\ &- \vert T_0 \cap T_1 \cap T_2 \cap T_3 \vert - \dots \\ &+ \vert T_0 \cap T_1 \cap T_2 \cap T_3 \cap T_4 \vert + \dots \\ &- \vert T_0 \cap T_1 \cap T_2 \cap T_3 \cap T_4 \cap T_5 \vert \end{align}

By symmetry, this is equal to:

\begin{align} S &= 6~\left\vert T_0 \right\vert \\& - {6 \choose 2}~\left\vert T_0 \cap T_1 \right\vert \\& + {6 \choose 3}~\left\vert T_0 \cap T_1 \cap T_2\right\vert \\& - {6 \choose 4}~\left\vert T_0 \cap T_1 \cap T_2 \cap T_3\right\vert \\& + {6 \choose 5}~\left\vert T_0 \cap T_1 \cap T_2 \cap T_3 \cap T_4\right\vert \\& - {6 \choose 6}~\left\vert T_0 \cap T_1 \cap T_2 \cap T_3 \cap T_4 \cap T_5 \right\vert \end{align}

Then with general counting arguments :

\begin{align} S &= \sum_{i=1}^6 {6 \choose i}\left\vert\bigcap _{j=0}^{i-1} T_j \right\vert(-1)^{i+1} \\ &= - \sum_{i=1}^6 {6 \choose i}~10^{6 - i} ~(-1)^i \\ &= 10^6 - \sum_{i=0}^6 {6 \choose i}~10^{6 - i} ~(-1)^i \\ &= 10^6 - (10 - 1)^6 \end{align}

So many lovely solutions above. For convenience in checking solutions by brute force, I offer the following Mathematica code,

Length[Select[ParallelMap[DigitCount[#][] &, Range[10^6]], # > 0 &]]


This code makes a list of all the numbers from 1 to 1,000,000, then checks the number of every digit in each of them (DigitCount), and throws away everything except the second digit ([]), as that's the one we care about in answering this question. It then Selects all the results with at least one 2, and counts how many are left. For the sake of speed, the code runs in parallel on as many cores as your Mathematica license allows.

For the problem as stated, it returns the answer 468559.

In the code as written, I check all integers up to and including 1,000,000, while the problem specified only integers up to and including 999,999. I did this because (a) it is trivially observed that there are no 2s in 1,000,000, so it wouldn't change our answer, and (b) 10^6 is quicker to type than 10^6-1.

the answer is $427608$ for the number with $2$ between $100000$ and $999999$. I create program to count the number with number two between $100000$ and $999999$. Here is the code I used

for (int num = 100000; num < 999999; num++)
{
if (num.ToString().Contains("2"))
{

• Your answer does not count $2$ which is less than $1,000,000$, yet contains the digit $2$.