83 arithmetic/digits/zeros/million.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
83 arithmetic/digits/zeros/million.p
How many zeros occur in the numbers from 1 to 1,000,000?
arithmetic/digits/zeros/million.s
In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)
numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of
which one tenth, or 9(n-1)10^(n-2), are zeroes. When we change the
range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in
10^n, gaining one zero, so
p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.
Solving the recurrence yields the closed form
p(n) = n(10^(n-1)+1) - (10^n-1)/9.
For n=6, there are 488,895 zeroes, 600,001 ones, and 600,000 of all other
digits.
Continue to:
My Books
