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

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

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.

Answer 4

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 $$

Answer 5

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

Answer 6

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.

Answer 7

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
>>> 

Answer 8

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 $$

Answer 9

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.

The problem asks to find

$$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}$$

Answer 10

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

Length[Select[ParallelMap[DigitCount[#][[2]] &, 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 ([[2]]), 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.

Answer 11

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"))
                {
                    numberWithTwo.Add(num);
                    count++;
                }
            }
            Console.WriteLine("Total number that contain number 2 is :"+ count);
            Console.ReadLine();