mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-06-23, 20:27   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2007-06-26, 22:44   #2
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

28116 Posts
Default

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)
Orgasmic Troll is offline   Reply With Quote
Old 2007-06-27, 17:51   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

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 is offline   Reply With Quote
Old 2007-07-09, 17:49   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default

An update:

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

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

[Would someone double-check this value?]
davar55 is offline   Reply With Quote
Old 2007-07-10, 00:11   #5
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by Orgasmic Troll View Post
if n = 10^{k+1} then there are...
don't you mean n=10^k-1 ?
m_f_h is offline   Reply With Quote
Old 2007-07-10, 00:27   #6
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by Orgasmic Troll View Post
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
except for the '0' we start with, the following code confirms your result & (corrected) formulae:
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 >
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.

Last fiddled with by m_f_h on 2007-07-10 at 01:26
m_f_h is offline   Reply With Quote
Old 2007-07-10, 04:08   #7
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by davar55 View Post
[Would someone double-check this value?]
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)
}
m_f_h is offline   Reply With Quote
Old 2007-07-10, 20:32   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

442410 Posts
Default

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)
petrw1 is online now   Reply With Quote
Old 2007-07-10, 22:13   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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)
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....)
m_f_h is offline   Reply With Quote
Old 2007-07-11, 04:12   #10
axn
 
axn's Avatar
 
Jun 2003

17·277 Posts
Default

Perhaps you're thinking about Benford's Law
axn is offline   Reply With Quote
Old 2007-07-11, 17:56   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

23·7·79 Posts
Default

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.
petrw1 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Help Find a Sequence? davar55 Math 2 2010-02-19 16:54
Find the Value davar55 Puzzles 7 2009-07-02 19:46
New way to Find (X^Y) % M maheshexp Miscellaneous Math 29 2004-08-30 15:59
New way to Find (X^Y) % M maheshexp Software 2 2004-05-08 03:16

All times are UTC. The time now is 00:18.

Fri Oct 23 00:18:11 UTC 2020 up 42 days, 21:29, 0 users, load averages: 1.49, 1.54, 1.61

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.