# Running Out of Digits, Level 3

The challenge idea is credited to HelloWorld1337.

You initially have x of each digit from 0 to 9. This means you have x * 10 digits in total. This count for each digit is shown in the table below.

Digit 0 1 2 3 4 5 6 7 8 9
# Remaining x x x x x x x x x x

Now start counting by ones, from 1. Each time you say a number you must remove the digits required to make the number from your stockpile of digits. For example, after you have counted from 1 to 13, the above table now looks like:

As an example, if you counted from 1 to 13 and didn't skip any numbers, the above table will look like:

Digit 0 1 2 3 4 5 6 7 8 9
# Remaining x-1 x-6 x-2 x-2 x-1 x-1 x-1 x-1 x-1 x-1

What is the largest number x you can count to without running out of the digits needed to form the number?

• Welcome to Puzzling! It seems you have two definitions of x as a variable - lowercase "x" for the number of digits left, and uppercase "X" for the largest number created. I'd suggested changing one of those to a different letter to avoid confusion. – bobble Feb 5 at 19:46
• Makes sense! Thank you. My intent is for those to be the same number; I've edited them accordingly. – 00Average Feb 5 at 20:01

I believe the answer is:

199,981. Mmm. Not this. You can add more and still work: 199,990

Details:

Short answer: I wrote a script. I know, I know.
Roughly, though, 1 in 10 of each digit is a 1. Consider 199,990. Take the last 5 digits of 199,990 and it gives you ~99,995 ones. To this add the 99,990 ones for the hundred-thousands place and you get ~199,985.
At this value, each additional number is adding 1 additional 1 (in the hundred-thousands place), so you can increase/decrease until you get a second 1 somewhere else. So this suggests that for $$x\in [199,981;199,990]$$ you use exactly $$x$$ 1s to write out the numbers from 1 to $$x$$.
When you go to 199,980 you will have 1 one left over. When you get to 199,991, you will be 1 one short.

Edit: Paul Panzer is correct. He should get the tick. Here's a justification:

If $$x = k\times10^n-1$$ then the number of ones needed is $$kn10^{n-1}$$ plus an additional $$10^n$$ if $$k\geq2$$.
This can be used to show that $$1\times10^9.
With a bit of care, you can now add $$2\times10^8$$ and discover that $$x$$ is less than that. But you can add $$1\times10^8$$, so $$x>1.1\times10^9$$.
Continue with that process and you get 1,111,111,110 as the maximum $$x$$

• Scripts are good! Long time lurker--always appreciate what the programming gang here comes up with to solve these kids of questions. I kind of figured someone would either have a script or some simple-but-elegant proof of why it is what it is. – 00Average Feb 8 at 14:20
• I think if Paul Panzer's answer is correct, then it's clearly a larger number than mine. I haven't checked it, but it looks good. – Dr Xorile Feb 8 at 17:51
• As per 00Average comments under his answer, seems like yours is correct, and Paul's answer corroborates your answer (visually). – justhalf Feb 9 at 8:31
• I've been second-guessing myself, but you both show that your answer is correct. At each new order of magnitude, the count equalizes at all nines (evident on Paul's plot at each 10^n), but then each time we add a digit, the total count of digits is front-loaded with ones, (also visible in his diagram) increasing faster than y=x. It's this front-loading that stops the count before we reach 1,111,111,110. – 00Average Feb 9 at 16:15

I'm pretty sure it's:

1,111,111,110

No proof, though, but a few remarks and a suggestive plot:

the number of ones will never be smaller than that of any other digit
for x of the form 99...99 (k digits) the distribution of 1,2,3,... is even each having been used exactly k x 10^{k-1} times; zeros will have occurred 11...12 (k digits) times less often.
for x of the form 11...10 (k digits) the number of ones used is k x 11...11 (k-1 digits)

• It looks like your plot validates Dr. X's answer, unless I'm missing something... Isn't the 1's count kissing (and ostensibly crossing) the line of y=x/total#ofdigits=number right around 200,000? It feels like this plot answered the question too, and I just needed to phrase it better. – 00Average Feb 8 at 16:26