mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Find the Value (https://www.mersenneforum.org/showthread.php?t=8477)

 davar55 2007-06-23 20:27

Find the Value

Consider the set of integers from 0 to n represented in decimal
with no lead zeros. Find the value of n > 1 such that the total
number of zeros in the representations equals n.

 Orgasmic Troll 2007-06-26 22:44

so here's what I do know..

if n = 999, then we have 99 0s from the ones digit and 90 0s from the tens digit

if n = 9999, we have 999 0s from the ones digit, 990 0s from the tens digit and 900 0s from the hundreds digit

if $$n = 10^{k+1}$$ then there are $$10^{k-1}-1$$ from the ones digit, $$10^{k-1}-10$$ from the tens digit, and so on, thus if $$n = 10^{k+1}$$, then we have accumulated $$\sum_{i=0}^{k-1} 10^{k-1} - 10^i$$ 0s, this equals $$k*10^{k-1} - \sum_{i=0}^{k-1} 10^i = k*10^{k-1} - \frac{10^k-1}{9}$$

now, somewhere in between 10^11-1 and 10^12-1, we have more 0s than n, in fact, we have 88,888,888,889 more 0s, so, assuming that the difference is monotone increasing (I believe it is, although I haven't checked formally) it has to happen for some 11 digit number (or it doesn't happen at all)

 davar55 2007-06-27 17:51

Please double-check that you don't mean some 12-digit number,
since the transition point is > 10^11 - 1.
And don't forget that 0 is part of the set, so you might need to
add 1 to the number of zeros.

 davar55 2007-07-09 17:49

An update:

Upon analysis, the number of zeros in the representations of integers
from 0 up to 99,999,999,999 is [spoiler]98,888,888,890[/spoiler].

Iterating from that point gives a match at
n = [spoiler]100,559,404,365[/spoiler].

[Would someone double-check this value?]

 m_f_h 2007-07-10 00:11

[quote=Orgasmic Troll;109065]
if $$n = 10^{k+1}$$ then there are...[/quote]
don't you mean n=10^k-1 ?

 m_f_h 2007-07-10 00:27

[quote=Orgasmic Troll;109065]
if n = 999, then we have 99 0s from the ones digit and 90 0s from the tens digit
if n = 9999, we have 999 0s from the ones digit, 990 0s from the tens digit and 900 0s from the hundreds digit[/quote]
[code]
gp > ^Z
Suspended
(mfh@lx08 ~/NumberTheory/PARI) php
<?=($a=count_chars(join(range(0,99))))?$a[48]:0,"
",($a=count_chars(join(range(0,999))))?$a[48]:0,"
",($a=count_chars(join(range(0,9999))))?$a[48]:0,"
";^D
10
190
2890
(mfh@lx08 ~/NumberTheory/PARI) fg
gp
gp > calc0mfh(k)=k*10^(k-1)-(10^k-1)/9+1
time = 0 ms.
gp > calc0mfh(3)
time = 0 ms.
%216 = 190
gp > calc0mfh(4)
time = 0 ms.
%217 = 2890
gp >
[/code]thus, the correct formula is:
number of '0's in {0,1,...,10^(k+1)-1} = k*10^(k-1)-(10^k-1)/9+1

I confirm your value for k=11 which is correct, i.e. seems to include the +1 already.
If your "iterations"(?) are ok, the result should be correct.

 m_f_h 2007-07-10 04:08

[quote=davar55;109946][Would someone double-check this value?][/quote]
it seems ok - I believe the following code is correct:
[code]cnt0(n) = { local( cnt=0, m=divrem(n,10)); if( n<10, return(1));
/* Let n = 10 m[1] + m[2]. Count 0's in m[1] and multiply this by m[2]+1: This
* is the number of 0's in { 10 m[1],..., n } minus 1 (trailing 0 of 10 m[1]).
*/
n=m; while( n=divrem(n[1],10), cnt += !n[2] ); cnt *= (m[2] + 1);
/* now add the number of 0's occuring in last position in {0,...,10 m[1]}
* (this is equal to 1+m[1]) plus 10 * the number of 0's in { 1,...,m[1]-1 }.
*/
cnt+1+m[1]+10*(cnt0( m[1]-1 )-1)
}
[/code]

 petrw1 2007-07-10 20:32

Without a lot of deep thought I surmised that there would be an equal distribution of digits in counting up from 1 ... but I discovered that, while that is the case it is not until 'n' gets VERY LARGE

For example: we get the correct number of digits of 1 at only n=199,981 and many more times as n increases.

However, digits 2 - 9 match much later ... 2 at 242,463,827; 3 at 371,599,983 (I haven't double checked these, though)

 m_f_h 2007-07-10 22:13

[quote=petrw1;110032]
For example: we get the correct number of digits of 1 at only n=199,981 and many more times as n increases.
However, digits 2 - 9 match much later ... 2 at 242,463,827; 3 at 371,599,983 (I haven't double checked these, though)[/quote]

I don't know if this is related but I once read that 1 is also the most common digit in any "random" collection of numbers (e.g. table of physical constants etc)
which has to do with the fact that the range [1,2) is "relatively" larger than [2,3) etc. (I don't remember well how exactly the argument was going - maybe w.r.t. scientific notation (x=m*10^e) or logarithmic scale or....)

 axn 2007-07-11 04:12

Perhaps you're thinking about [URL="http://mathworld.wolfram.com/BenfordsLaw.html"]Benford's Law[/URL]

 petrw1 2007-07-11 17:56

When I wrote a simple program to simply go through all values of n starting from 1 and counting the occurence of each digit, whenever I got to a n of 99...99 the total number of each digit from 1 to 9 was the same with 0 consistently trailing ... but gaining.

n=9: 0=0; 1-9=1
n=99: 0=9; 1-9=20
n=999: 0=189; 1-9=300
n=9999: 0=2889; 1-9=4000
n=99999: 0=38889; 1-9=50000
....
and the pattern continues.

I think I just described in layman terms what the true mathemiticians described earlier in formulae.

All times are UTC. The time now is 20:40.