How many zeros (10^666)! ends in?
Sam Atabaki
This is regarding a problem that was posted a few days ago.
Problem is: How many zeros does the number (10^666)! (! is factorial)
ends in. A solution follows
Let X=(10^666)!
Then X=1*2*3.....*(10^666). X's terminating zeros are obtained in two
ways:
1. Components of X that end in zero(s)
2. Components of X that end in five(s). (since any number
ending in 5 multipied by an even number, results in an
added terminating zero)
NOTE: Throught this article I'm using the term "component", or "element"
to refer to the numbers comprising the factorial, i.e.,
1, 2, 3,....., and 10^666.
In this solution we will count the number of numbers less than 10^666
(elements of the factorial) that end in exactly one zero (call it x1),
the number of numbers less than 10^666 that end in exactly 2 zeros
(call it x2), exactly 3 zeros (x3), ...., and exactly 666 zeros (x666).
Then obviously X's number of terminating zeros resulted from its
zero-terminated components is: x1 + 2*x2 + 3*x3 +.....+666*1.
Furthermore, there will be an additional terminating zero for X, for
every 10 of its components, generated by the 5-terminated elements.
(For example, 10! is equal to 3628800, which has two terminating
zeros; one because of the element "10", and one because of the element
"5").
Therefore, the number of X's terminating zeros resulted from
5-terminated elements is: 10^666/10 = 10^665 (interesting!!!!!!!!!)
Now, let's count the number of X's terminating zeros resulted from
zero-terminated elements:
It is not hard to show that for numbers LESS than 10^n (n>=1), there
are
[9^(n-0) -9]/8 numbers that end in exactly one zero.
[9^(n-1) -9]/8 numbers that end in exactly two zeros.
[9^(n-2) -9]/8 numbers that end in exactly 3 zeros.
.
.
.
[9^2 -9]/8 numbers that end in exactly (n-1) zeros.
and only 1 number that ends in exactly (n) zeros.
Thus, the number of terminating zeros for X is the sum of
terminating zeros caused by "5"-terminated elements and "0"-terminated
elements (n=666):
10^665 + 1*{[9^(666-0) -9]/8} + 2*{[9^(666-1) -9]/8} +
3*{[9^(666-2) -9]/8} +...+ 665*{[9^(666-664) -9]/8} + 666*1
I have not yet been able to find a closed form for the answer.
All comments are welcome.
-Sam K. Atabaki
Dr. Science
of five among the numbers from 1 to 10^666. If a number is divisible
by 5^k but not 5^(k+1), then it contributes k zeros to the product.
The number of numbers between 1 and N which are divisible by d is [N/d],
where the brackets represent the greatest integer function. From this,
it is not hard to see that the number of zeros in N! is given by
Sum { [N/5^k] : k = 1,2,3,...}. If you eliminate the brackets, you
get a geometric series whose sum is N/4. This is a very good estimate;
it can be shown that it is off by at most log N / log 5 + 2.
Thus, (10^666)! ends in 2.5 * 10^665 - r zeros, where r is between 1 and 1000.
I used Maple to determine the exact value of r:
|\^/| MAPLE V
_|\| |/|_. Copyright (c) 1981-1990 by the University of Waterloo.
\ MAPLE / All rights reserved. MAPLE is a registered trademark of
<____ ____> Waterloo Maple Software.
| Type ? for help.
> sum:=0:
> N:=10^666:
> for i from 1 by 1 while N>1 do
> N:=trunc(N/5):
> sum:=sum+N
> od:
> sum;
249999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999857
So as you can see, the exact number of trailing zeros is 2.5 * 10^665 - 143.
--
David Radcliffe
radc...@csd4.csd.uwm.edu
C.E. Thompson
|>
|> The number of numbers between 1 and N which are divisible by d is [N/d],
|> where the brackets represent the greatest integer function. From this,
|> it is not hard to see that the number of zeros in N! is given by
|> Sum { [N/5^k] : k = 1,2,3,...}. If you eliminate the brackets, you
|> get a geometric series whose sum is N/4. This is a very good estimate;
|> it can be shown that it is off by at most log N / log 5 + 2.
|>
|> Thus, (10^666)! ends in 2.5 * 10^665 - r zeros, where r is between 1 and 1000.
|> I used Maple to determine the exact value of r:
Another way of looking at this is that the above sum is (N-s_5(N))/4, where
s_5(N) is the sum of the digits of N expressed in base 5. Expressing 10^666
in base 5 (I used dc, if you want to know) gives
34004 10314 23234 44031 33342 10324 32404 04103 41210 23000 30412 23214
03432 13101 41411 20023 40024 03033 02120 10410 11111 23322 33321 30221
42310 11313 04102 33042 33333 00214 14402 31101 02444 03011 40221 44110
30134 02413 34414 12120 34143 00313 00210 12423 34112 03411 04330 20023
41011 40203 23404 03443 02323 44124 33434 00443 00233 24 followed by 666 zeroes
so that s_5(10^666) = 57*1 + 46*2 + 65*3 + 57*4 = 572, in agreement with
|>
|> So as you can see, the exact number of trailing zeros is 2.5 * 10^665 - 143.
|>
One advantage of looking at things this way is that it enables you to see
when the number of zeroes attains its minimum and maximum shortfalls from
N/4. rec.puzzlers might like to try the following problem: what can you
say about the N for which the last non-zero digit of N! in base 12 is
even, and those for which it is odd?
Chris Thompson
JANET: ce...@uk.ac.cam.phx
Internet: ce...@phx.cam.ac.uk
T.M. Speight
One advantage of looking at things this way is that it enables you to see
when the number of zeroes attains its minimum and maximum shortfalls from
N/4. rec.puzzlers might like to try the following problem: what can you
say about the N for which the last non-zero digit of N! in base 12 is
even, and those for which it is odd?
As a sideline, it is interesting to note that 1 is the only value for
k such that the last nonzero digit of k! _IN_BASE_10_ is odd:
There are more even numbers than multiples of 5. Similarly, there are
more multiples of 2^n than 5^n for any n>0 (proof left to others). A
point to note, though, is that in this special case, there are at least
twice as many 2's as 5's in the prime factorisation of k! for all
k>=2.
This means, for k in this range, that k! = 5^m.2^n.Q [Q is a
quotient, not divisible by 5 or 2] and n>=2m. Therefore
k! = 20^m * 2^(n-2m) * Q
Now 20 times any number not a multiple of five has an even
last-nonzero-digit, so any k!>1! has an even last-nonzero-digit.
To consider the base-12 system, note that 12=2*2*3
Let n! = 2^i * 3^j * Q [ Q not mult. of 2 or 3 ]
n i j
== == ==
1 0 0
2 1 0
3 1 1
4 3 1
5 3 1
6 4 2
7 4 2
8 7 2
9 7 4
A 8 4
B 8 4
10 A 5
11 A 5
12 B 5
13 B 6
Observe i>=2j
C.E. Thompson
(T.M. Speight) writes:
|>
|> To consider the base-12 system, note that 12=2*2*3
|>
|> Let n! = 2^i * 3^j * Q [ Q not mult. of 2 or 3 ]
|>
|> n i j
|> == == ==
|> 1 0 0
|> 2 1 0
|> 3 1 1
|> 4 3 1
|> 5 3 1
|> 6 4 2
|> 7 4 2
|> 8 7 2
|> 9 7 4
|> A 8 4
|> B 8 4
|> 10 A 5
|> 11 A 5
|> 12 B 5
|> 13 B 6
|>
|> Observe i>=2j
But my dear chap... your table shows that i < 2j when n = 3, 9, or 15 (or
13 as you call it, but I see no reason no write everything in base 12 just
because we are arguing about the expression of n! in base 12). It happens
again for 27<=n<=31.
In fact, your i = n-s_2(n) and j = (n-s_3(n))/2, where s_b(n) is the sum
of the digits of n in base b. Therefore i < 2j happens when s_3(n) < s_2(n).
Most of the time, this isn't true, because a "normal" number has
s_3(n) ~ log(n)/log(3) and s_2(n) ~ log(n)/log(4), but it will happen
infinitely often: for example, whenever n is a power of 3. An exact
analysis of the density of the set leads into unsolved problem area, as
questions involving the simultaneous representation of numbers in more than
one base usually do.