[Math] How many numbers between 1 and 150 contain the digit ‘1’ in their base 10 representation

puzzlerecreational-mathematics

For curiosity my nephew made me this question and I write down every number between $1$ and $150$ and I have found $\{1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31, 41, 51, 61, 71, 81, 91, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150\}$.

I realize some intriguing facts about the sequence but i don't know what mathematical law can be applied to it.

Best Answer

Mathematical "law" is not well defined in this context. I guess you are after a formula or an algorithm (other than listing all numbers) that gives us the result for any arbitrary integer $n \ge 0$. Yes, we can find one, and I'll describe it in the end. Here's my reasoning and how I got there:

Start counting at $0$.

We notice that every ten numbers we get one number that has a '1' in it, except for one particular/special set of ten numbers that has all 10 numbers with a '1' (these are the numbers $10$ to $19$). In other words from $0$ to $9$ we have 1 number with a '1' in it, from $10$ to $19$ all numbers have '1', from $20$ to $29$ we have one number with '1' in it and so on.

So for the first one hundred numbers ($0$-$99$) we get $9\times 1 + 10= 19$ numbers that have '1' in them. And this happens for every one hundred numbers, except for one particular/special set of 100 numbers that all of them have a '1' (these are numbers $100$ to $199$).

We can do the same process for the first 1000 numbers, the first 10,000 numbers and so on. And we can see the general pattern: the number of '1' depends on what we have found in the previous 'level'. So in general, for every $10^r$ numbers, we get $S_r$ numbers that have '1' in them. $S_r = 9\times S_{r-1} + 10^{r-1}, \text{with } S_0=0$. Except one particular/special set of $10^r$ numbers where all of them have a '1' in them.

Here are the values for the first few $S_r$ $$\begin{align} S_1 &= 1 \\ S_2 &= 9\times 1 + 10 = 19 \\ S_3 &= 9\times 19 + 100 = 271 \\ S_4 &= 9\times 271 + 1000 = 3439 \end{align}$$ There are ways to find a closed formula from a recursive formula, but I do not find it necessary to complicate things at this point, since we can quickly and easily calculate any $S_r$.

We notice that every number $n$ can be broken into units, tens, hundreds, thousands, etc. For example, $251$ can be broken in 2 hundreds, 5 tens, and one unit. Two hundreds means that we have two groups of $100(=10^2)$ numbers. How many numbers in these two groups have '1' in them? We know that at least one group has $S_2$ numbers that have '1' in them (it's a 'normal' group). The other group has either another $S_2$ (it's a normal group) or another $100$ numbers (it's a special group) that have '1' in them. It's easy to see that if the hundreds are above 1 then the "special" hundreds are always included. So we should have $100 + S_2$ for our first 200 hundred numbers. Then we can move to the tens. We have 5 of them. Similarly, since we are above 1 ten, we have the special group and 4 regular groups, meaning we have another $4\times S_1 + 10$ numbers that have '1' in them. Finally we have 1 unit, which means we have yet another number with '1' in it. Final result is 134.

There is a tricky situation when we have just one hundred, or just one ten, just one of any group. For example, think about $n=1033$. We realise that the first thousand from 0-999 has $S_3$ numbers with '1' in them, and all the rest 1000-1034 (that is 34 numbers) all have '1' in them.

Here's the general algorithm:

Let's have an integer $n$ that is represented with $k$ digits in base 10 as $(d_{k-1}\cdots d_1d_0)_{10}$.

Starting from the most significant digit and an intermediate result of zero, we apply these rules:

  • If digit $d_i=0$ we move on to the next digit.
  • If digit $d_i = 1$ then we have $S_i + (d_{i-1}\cdots d_0)_{10} +1$ numbers that have '1' in them. $\text{Final answer} = S_i + (d_{i-1}\cdots d_0)_{10} +1 + \text{intermediate result}$. Stop.
  • If $d_i > 1$ then $(d_i-1)S_i + 10^i$ numbers have '1' in them. $\text{intermediate result} = (d_i-1)S_i + 10^i + \text{intermediate result}$. We continue with the next digit in the sequence.
  • If there are no more digits we stop, and the intermediate result is our final answer.

Let's see some examples:

Take the number $n=150$, which means $d_2=1, d_1=5, d_0 = 0$

  • $d_2=1$ so $\text{Final answer} = S_2 + (50)_{10} +1 + \text{intermediate result} = 19 +50 + 1 + 0 = 70$

Let's see a more complicated example $n=4561$.

  • $d_3=4$, so intermediate result $= (d_3-1)S_3 + 10^3 + \text{intermediate result} = (4-1) \times 271 + 1000 + 0 = 1813$. Moving to the next digit.
  • $d_2=5$, so intermediate result $= (d_2-1)S_2 + 10^2 + \text{intermediate result} = (5-1) \times 19 + 100 + 1813 = 1989$. Moving to the next digit.
  • $d_1=6$, so intermediate result $= (d_1-1)S_1 + 10^1 + \text{intermediate result} = (6-1) \times 1 + 10 + 1989 = 2004$. Moving to the next digit.
  • $d_0=1$, so Final answer $= S_0 + (d_{-1}\cdots d_0)_{10} +1 + \text{intermediate result} = 0 + 0 + 1 + 2004 = 2005$.

I hope this answers your question. Let me know in the comments if you would like clarifications on any part.

Related Question