[Tutor] Fwd: Need help with Factorial algorithm using Python

[Luke Paireepinart]

Oops, accidentally replied off list.

---------- Forwarded message ----------
From: Luke Paireepinart <rabidpoobear at gmail.com>
Date: Thu, Sep 4, 2008 at 9:39 AM
Subject: Re: [Tutor] Need help with Factorial algorithm using Python
To: Robert Berman <bermanrl at embarqmail.com>




On Thu, Sep 4, 2008 at 8:59 AM, Robert Berman <bermanrl at embarqmail.com>wrote:

>  I am using both the THINK PYTHON text and the Challenge-You website to
> learn Python. I am doing reasonably well and certainly enjoy the available
> challenges.
>
> I am currently attempting to work a challenge known as the 'Zeros of a
> Factorial' challenge located at
> http://www.challenge-you.com/challenge?id=484. The actual challenge is as
> follows: "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.
>
> I need to know if I am even close with my approach to a workable algorithm
>
Sort of, but you're just guessing-checking or brute-forcing, which is not a
really elegant algorithm.  It will eventually come up with the right answer,
though.
You could also do a binary-search of sorts.  Like, double the number, check
the factorial.  If it has too few trailing zeroes, double it again.  Once
you get above the target trailing zeroes, use 1.5 of the previous amount
(instead of doubling).  If you have too many zeroes still, use 1.25 of the
previous amount.  Otherwise use 1.75.  That should converge fairly quickly
on the correct answer.


> and whatever suggestions you might have to speed up the process so that it
> would not take hours until it found the correct integer. Any and all
> suggestions as well as more efficient ways to code the algorithm will be
> most appreciated.
>

Take a look at the code I've attached.  It will search through all the
factorials from 0 to 1000 that are multiples of 5.  See if you can see the
pattern in the number of zeroes.  See hint below if you want.

Once you figure out the pattern, you can just extrapolate from the 7**20
trailing zeroes what the actual factorial number is, then you can check it
and make sure it's correct.

I wrote a recursive factorial in case you're interested in seeing it.  It's
in the code.  Hits the maximum recursion depth at factorial(1000).

Oh, I also used a different strategy than you to count the zeroes.  I just
used a regex, because that made the most sense to me at the time.

If any of my code doesn't make sense, let me know.
Figuring out the pattern is better than a smarter guess-and-check, because
you can go straight from a number of trailing zeroes directly to the source
factorial.




 (hint: they are consecutive in groups of 5, and sometimes they skip one
trailing zero, and sometimes two, between groups of 5.  Try iterating over
all the numbers between each gap and figure out which one creates the
missing trailing zeroes, and study all these values.)
You could probably look this stuff up online, but I thought it'd be more fun
to try to come up with an algorithm on your own.  (I didn't look this up
either, so there might be a point at which the factorial pattern I am
talking about breaks down, but I don't think there should be.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20080904/b1605ac0/attachment.htm>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: factorial.py
URL: <http://mail.python.org/pipermail/tutor/attachments/20080904/b1605ac0/attachment.txt>