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.
$\begingroup$
$\endgroup$
6
-
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$– user40528Jun 21, 2020 at 20:14
-
1$\begingroup$ If my number has 12 digits does 100120000007 count? $\endgroup$– Bernardo Recamán SantosJun 21, 2020 at 20:23
-
$\begingroup$ digit is only 0-9 so 150/ 12 in above example is not valid $\endgroup$– ThomasLJun 21, 2020 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-GuestJun 21, 2020 at 21:03
-
2$\begingroup$ should this question perhaps say "positive integers"? $\endgroup$– JDLJun 22, 2020 at 8:39
|
Show 1 more comment
5 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jun 21, 2020 at 22:16
-
2
$\begingroup$
$\endgroup$
4
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.
answered Jun 21, 2020 at 20:18
-
$\begingroup$ your answer is correct, but there is another clever way to get this result... $\endgroup$– ThomasLJun 21, 2020 at 20:40
-
$\begingroup$ What about a 10-digit number containing the digits
10in order, etc.? $\endgroup$ Jun 21, 2020 at 20:49 -
-
$\begingroup$ There are no 10 digit numbers less than 1,000,000,000. $\endgroup$– JDLJun 22, 2020 at 8:38
$\begingroup$
$\endgroup$
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$$
answered Jun 21, 2020 at 22:19
$\begingroup$
$\endgroup$
2
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.
-
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, 2020 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-GuestJun 22, 2020 at 3:04
$\begingroup$
$\endgroup$
1
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.
answered Jun 22, 2020 at 8:06
-
$\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$ Jun 27, 2020 at 10:45