[Tutor] Need help with Factorial algorithm using Python
carroll at tjc.com
Fri Sep 5 07:20:03 CEST 2008
On Thu, 4 Sep 2008, Robert Berman wrote:
> "It can easily be seen that 6! = 720 and has exactly one
> trailing zero. What is the lowest integer, x, such that x! has 7^20
> trailing zeros?"
> It does not, on the surface, appear to be a frontal lobe breaker. Design
> an algorithm to build factorials; count the number of trailing zeros, and
> the first time we hit it, we have the lowest integer. To test, I computed
> factorials for 50,000--12,499 trailing zeros,100,000 trailing
> zeros--24,999, 150,000 trailing zeros 37,498, and finally 200,000
> trailing zeros of 49,998.
> Obviously, running a test on 1000000 would take some time and would not
> even be close to the required number of trailing zeros.
At the risk of spoiling with a solution (don't worry, all code is at the
end), the trick here is to realize that this is all about counting 5's.
you get a zero on the end when a 10 gets into the factorial; and
a 10 factors down to 2 x 5. At first glance, you'd have to count both 2s
and 5s, but 2s are so plentiful in comparison to 5s, that you really only
need to count 5s.
So 5! has one 5, at 5. For that matter, so does 6!, 7!, 8! and 9!. All
of those will have only one trailing zero.
At 10! you have another 5, and now have 2 trailing zeroes; at 15!, you
have 3; and at 20! you have 4.
25!, however, gives you 6 zeroes. That's because 25 = 5*5, so it's giving
you 2 more fives instead of just one. 30! will get you 7 zeroes, etc.
Here's how I started thinking about it:
every 5 is worth one five.
every 25 is worth 5 fives, plus one more five, for a total of 6 fives;
and that score includes all numbers below it.
every 125 is worth 5 twenty-fives, plus one more five, for a total of 31
What does this get us? Well, let's say you want to know how many terminal
zeroes in 290!. 290 is 2*125 + 1*25 + 3*5. A 125 is worth 31; a 25 is
worth 6; and a 5 is worth 1; 2*31 + 1*6 + 3*1 = 71, so there should be 71
That turns out to be right:
[some code snipped]
>>> f = fact(290)
>>> print f, num_trailing_zeros(f)
So here's my routine to address the problem. It consists of making a
multiplication table of coefficients that includes the factor such as 5,
25, 125, etc., and their values (1, 6, 31, etc). Then, starting with the
highest ones first, successievely determining how many times each factor
goes into the number of zeroes. For example, to do the prior example
working backwards, what factorial will give you 71 zeroes?
Well, 71/31 gives you 2, remainder 9; so we know there are 2 125s;
9/6 gives you 1, remander 3; so we know there is 1 25;
3/1 gives you (duh) 3, so there are 3 5s.
so the answer to the question "what is the first factorial with 71
trailing zeros?" is 2*125 + 1*25 + 3*5 = 290; i.e. 290!
This function returns a lowest value N for which N! terminates
with num_z zeroes
i.e., find_lowest_factbase(2) = 10; because 10! = 3,628,800
coefflist is a list of lists, each sublist of which has two elements:
0: value of 5**N
1: weight of value
for i in range(1,1000000): #will break out well before a million
value = 5**i
if i == 1:
weight = 1
weight = (coefflist[-1]*5)+1
if weight > num_z:
for L in coefflist:
(quotient, remainder) = divmod(zerosleft, L)
zerosleft = remainder
for pair in productpairs:
product = product + pair*pair
I tested it by comparing the output of the two sets, one testing through
45! and one testing through 10 zeros (which works out to be the same):
for i in range(1,n+1):
m = m*i
s = str(n)
s_no_zeros = s.rstrip('0')
numz = len(s)-len(s_no_zeros)
for i in range(1,50):
k = fact(i)
nz = num_trailing_zeros(k)
if nz > max_nz:
print "nz=%s at %s! (%s)" % (nz, i , k)
max_nz = nz
for i in range(1,11):
k = find_lowest_factbase(i)
print "nz=%s at %s! (%s)" % (i, k , fact(k))
And your answer?
>>> print "answer: ", find_lowest_factbase(7**20)
More information about the Tutor