# 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? –  abligh Feb 9 at 23:39
Do you mean integers > 0? –  Shahar Feb 9 at 23:59
Answer confirmed to be 468559. ideone.com/fb5173 –  Shahar Feb 10 at 0:04
There are infinite negative integers that have the digit 2 too –  Lưu Vĩnh Phúc Feb 10 at 0:58
python: reduce(lambda x,y:x+y, [1 for x in xrange(1000000) if '2' in str(x)]) –  ldrumm Feb 10 at 2:19

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$ $4$-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. –  canaaerus Feb 9 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. –  Cameron Buie Feb 9 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. –  canaaerus Feb 9 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 –  BeowulfNode42 Feb 9 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). –  Cameron Buie Feb 9 at 22:07

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$? –  Cameron Buie Feb 9 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 at 20:45
can you give me one reference where I can learn this kind of things? (counting+recurrences) –  Vicfred Feb 14 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 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. –  Vicfred Feb 14 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 –  BeowulfNode42 Feb 9 at 21:35

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 –  zinking Feb 10 at 7:03
@zinking: It's worth noting that this is exactly WimC's approach, in less compact form. –  Cameron Buie Feb 10 at 13:01
@CameronBuie getting it now, that's better, but the first pass I didn't get it, how dumb. –  zinking Feb 10 at 15:05
ideone.com/AcV9PR refer this if you want calculations –  zinking Feb 10 at 15:06
I see Pascal's Triangle on that bottom equation reduction. I need to take a break from math... –  Cole Johnson Feb 10 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. –  A. Donda Feb 10 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. –  Sam Beckman Feb 11 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) –  Cole Johnson Feb 10 at 17:00

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

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


Essentially, it makes a list of all the numbers from 1 to 1,000,000, then it 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 this case. It then Selects all the results with at least one 2, and counts how many are left.

For the problem as stated, it returns 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.

-

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

-

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

Your answer does not count $2$ which is less than $1,000,000$, yet contains the digit $2$. –  robjohn Feb 10 at 6:33