2008/9/5 Terry Carroll <[EMAIL PROTECTED]>:
> 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?
I think there is a simpler solution :-)
You can count the number of fives in the prime decomposition of a
number by just dividing by 5 repeatedly until you don't get a whole
number.
You can then find n such that n! has x zeroes by just starting with
n=0 and counting up, adding the appropriate amount at each step.
Code:
from __future__ import division
import operator
def fac(n):
""" Return n! """
return reduce(operator.mul, range(1, n+1))
def zeroes(n):
""" Count number of zeroes in n! """
f = fac(n)
return len(str(f))-len(str(f).rstrip('0'))
def fives(n):
""" Count number of 5s in prime factor decomposition of n. """
i = 0
while (n/5) == (n//5): # note future division in effect
i += 1
n = n//5
return i
def zeroes_inv(x):
""" Return n such that zeroes(n) == x. """
i = 0
count = 0
while count < x:
i += 5
count += fives(i)
return i
Although I am curious to know how long it took your algorithm to find
the answer for 7**20 ...
--
John.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
