[Tutor] Need help with Factorial algorithm using Python

[John Fouhy]

2008/9/5 Terry Carroll <carroll at tjc.com>:
> 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.