10
$\begingroup$

How many positive integers less than 1,000,000,000 contain their length as part of their digit string?
Example: 123466 has a length of 6 and 6 is one of its digits. Hence this number needs to be counted.

$\endgroup$
  • 2
    $\begingroup$ Do you mean that it's length is one of its digits? Or would any 150 digit number starting with 150 count as its length being part of its digits? $\endgroup$ – user40528 Jun 21 at 20:14
  • 1
    $\begingroup$ If my number has 12 digits does 100120000007 count? $\endgroup$ – Bernardo Recamán Santos Jun 21 at 20:23
  • $\begingroup$ digit is only 0-9 so 150/ 12 in above example is not valid $\endgroup$ – ThomasL Jun 21 at 20:35
  • $\begingroup$ I don’t think this question is worded correctly, then — to me, @BernardoRecamánSantos and postmortes’ conjectures are both valid; and nowhere in the question does it say the length needs to be a single digit. Your question asks “How many integers less than 1,000,000,000 contain their length as part of their digit string?” instead of what you’ve actually asked. $\endgroup$ – El-Guest Jun 21 at 21:03
  • 2
    $\begingroup$ should this question perhaps say "positive integers"? $\endgroup$ – JDL Jun 22 at 8:39
16
$\begingroup$

For any $d$ the number of integers of length up to $k$ with no digit $d$ (where $1\leq d\leq9$) is $9^k$ since each of the $k$ digits (padding at left with zeros if need be) is allowed to be one of 9 things. Hence, the number of length exactly $k$ with no digit $d$ (for any particular $d$) is $9^k-9^{k-1}$. This is true in particular when $d=k$, so the number of length-$k$ numbers not containing their length (when $1\leq k\leq9$) is also $9^k-9^{k-1}$, and therefore the number of length-$k$ numbers that do contain their length is $(10^k-10^{k-1})-(9^k-9^{k-1})$ which we might prefer to write as $(10^k-9^k)-(10^{k-1}-9^{k-1})$. Summing this for $k$ from 1 to 9 we get $(10^9-9^9)-(10^0-9^0)=10^9-9^9$.

This equals

612579511, a figure already found by Glorfindel by looking it up in OEIS, but as can be seen above the calculation is very straightforward.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Hurray for telescoping series! $\endgroup$ – humn Jun 22 at 3:15
10
$\begingroup$

The answer is

612579511

Reasoning: there are

  • 1 number of length 1 with digit 1
  • 18 numbers of length 2 with digit 2 (12, 22, ... 92, and 20 ... 29, but don't count 22 twice!)
  • 252 of length 3 with digit 3 (90 ending on 3, 81 where the middle digit is 3 but the last one isn't, 81 where the first digit is 3 but the last two aren't)
  • We could enumerate the rest, but that would be tedious. Fortunately, the sequence is in OEIS ...
  • 4: 3168
  • 5: 37512
  • 6: 427608
  • 7: 4748472
  • 8: 51736248
  • 9: 555626232
  • Summing them gives the final answer.

| improve this answer | |
$\endgroup$
  • $\begingroup$ your answer is correct, but there is another clever way to get this result... $\endgroup$ – ThomasL Jun 21 at 20:40
  • $\begingroup$ What about a 10-digit number containing the digits 10 in order, etc.? $\endgroup$ – Rand al'Thor Jun 21 at 20:49
  • $\begingroup$ only digits from 0 to 9 are allowed. $\endgroup$ – ThomasL Jun 21 at 21:03
  • $\begingroup$ There are no 10 digit numbers less than 1,000,000,000. $\endgroup$ – JDL Jun 22 at 8:38
8
$\begingroup$

There is an other way to find the solution.

Since we are limited to digit $0-9$, we are interested by the numbers between $1$ and $999,999,999$. We now remove the numbers that doesn't satisfy the condition. How many 1 digit numbers doesn't have the number $1$ in it? There are $8$ such numbers.
How many 2 digits numbers doesn't have the number $2$ in it? There are $8\times9$ such numbers. How many 3 digits numbers doesn't have the number $3$ in it? There are $8\times9\times9$ such numbers. More generaly, how many k digits numbers doesn't have the number $k$ in it? There are $8\times9^{k-1}$ such numbers. Our answer is $$999,999,999-8-8\times9-8\times9^2-8\times9^3-8\times9^4-8\times9^5-8\times9^6-8\times9^7-8\times9^8=612,579,511$$

| improve this answer | |
$\endgroup$
4
$\begingroup$

Given any positive integer,

it is always possible to construct another integer with that many digits that includes the original integer itself.

Therefore, there are at least

as many such integers as there are all integers altogether.

There cannot be any more than that, because the resulting integers are, well, integers.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Note that this answer was written before the question was edited to specify integers up to 10^9. $\endgroup$ – Gareth McCaughan Jun 21 at 22:08
  • $\begingroup$ This one gets an upvote from me as well, because based on the original parameters of the question it is most correct! $\endgroup$ – El-Guest Jun 22 at 3:04
3
$\begingroup$

If you

pad the numbers with leading zeroes so that they always have 9 digits

then it becomes easier to count how many there are because you then don't have to split it into cases.

There are $10^9$ strings of 9 digits. Those that start with one or more zeroes represent numbers with fewer digits.

There are $9^9$ strings of consisting of the digits $0$ to $8$. Any such string uniquely corresponds to a number not containing its length: If its length is $n$, just increment every digit that is $n$ or greater (the length is not affected by incrementing non-zero digits so this process is reversible).

Therefore there are $10^9-9^9$ numbers containing its own length as a digit at least once.

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for the first direct method. Another way: taking all numbers with digits 0-8, i.e. digits 0-9 but excluding digit 9, then replacing the digits matching the length with digit 9, you get all number with digits 0-9 but excluding its own length. $\endgroup$ – Florian F Jun 27 at 10:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.