0

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.

Thanassis
  • 3,175
Vinicius L. Beserra
  • 527
  • 1
  • 5
  • 14
  • I find it unclear what you're asking. You seem to already know how many numbers there are since you've listed them all out. – BHT Sep 22 '16 at 01:11
  • Any number from 100 to 150 contains 1, so that gives 51. Any number from 10 to 19 has a 1, so that's another 10. Then, from 1 to 99, there are 10 numbers that end in 1, so that's another 10. However, we have counted the number 11 twice (once since it is between 10 and 19, and the second time for ending in 1). So we have 51+10+10-1=70. – user2825632 Sep 22 '16 at 01:11
  • Thanks but Is there a way to modelate it mathematically? – Vinicius L. Beserra Sep 22 '16 at 01:14
  • 1
    Use the inclusion/exclusion principle on the number of 1's. First count how many contain at least one 1, then subtract those with at least two 1's, add those with three 1's, etc. – Parcly Taxel Sep 22 '16 at 01:21
  • 1
    Thing is, usually, patterns and truths about the digits of numbers don't hold a lot of mathematical depth and don't give a lot to talk about. So there's not a lot more to say "mathematically" that what user2825632 has said. – JKEG Sep 22 '16 at 01:42
  • Thanks. I already knew it. I just wanna know to use math to find it more elegantly. – Vinicius L. Beserra Sep 22 '16 at 01:42
  • @ViniciusL.Beserra I am wondering whether my answer and my algorithm to find the answer for any number quickly, fully answers your question. – Thanassis Nov 02 '16 at 00:13
  • You could see this question and this question for ideas on how to count over larger ranges. – Ross Millikan Nov 12 '16 at 16:14

2 Answers2

4

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.

Thanassis
  • 3,175
1

Well, from what I know, there isn't a "law" to make this kind of problems, but you can solve it in a better way than listing all:

For example:

  • Count the numbers of one digit that have a 1.

You only have one number that is here: 1

  • Count the numbers with two digits that have only one $1$. Then you add the only number of two digits with two $1$'s ($11$).

If the number is of the type $\overline{1x}$, then you can add any number from $\{0,2,3,4,\dots,9\}$, that are $9$ numbers, so you have $9$ number that apply. If the number is of the type $\overline{y1}$, then $y$ could be any from $\{ 2,3,\dots,9\}$, that are $8$ possibilities. Then you have 17 numbers plus the $11$, so you have 18.

  • Finally count the numbers with three digits that have at least one $1$.

Well, this is easy because all numbers from $100$ to $150$ have a $1$, so you add $51$ numbers.

Then, add all: $1+18+51=70$.

(I don't know if this could help you, but I wasn't able to add this as a comment.)

iam_agf
  • 5,438