[Tutor] Need help with Factorial algorithm using Python

[Terry Carroll]

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 
fives.

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 
zeroes.

That turns out to be right:

[some code snipped]
>>> f = fact(290)
>>> print f, num_trailing_zeros(f)
60316116183878209766117976235613285674586630483425933084029202472047670485819885
24516473184964281054847594152584009528621417952272159399012893011898232929436576
79285114407298493208021847117743304953755459586044474858941338130407530467578458
33254416671760299033093062086252031499964109155039154660288221882477747977319966
16183514677158049698159171977934429370558012376711563782210013569092594615762035
60549776040291140480868660361895305429328142835207067479091087183725251309232283
59166396038270919098494331151103662489600000000000000000000000000000000000000000
000000000000000000000000000000 71

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!

Code:

def find_lowest_factbase(num_z):
    '''
    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=[]
    '''
    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
        else:
            weight = (coefflist[-1][1]*5)+1
        if weight > num_z:
            break
        coefflist.append([value, weight])
    coefflist.reverse()

    productpairs=[]
    zerosleft=num_z
    for L in coefflist:
        (quotient, remainder) = divmod(zerosleft, L[1])
        productpairs.append([quotient, L[0]])
        zerosleft = remainder
    product=0
    for pair in productpairs:
        product = product + pair[0]*pair[1]
    return product

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):

def fact(n):
    m=1
    for i in range(1,n+1):
        m = m*i
    return m

def num_trailing_zeros(n):
    s = str(n)
    s_no_zeros = s.rstrip('0') 
    numz = len(s)-len(s_no_zeros)
    return numz

#brute force: 
max_nz=0
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

# fives-algorithm:

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)
answer:  319169065190448050