<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#3333ff">
<font size="+1">Thank you very much for the help and the math
explanation from Omer. Much of my math background is based on brute
force methodology. Obviously, things have changed. Really changed.<br>
<br>
Time to do some reading about regex. And here I thought I was slick
working with lists and strings.<br>
<br>
Robert<br>
<br>
</font><br>
Luke Paireepinart wrote:
<blockquote
cite="mid:dfeb4470809040739j10b5b115x1fefe52fa6b2dc1c@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<br>
<div class="gmail_quote">On Thu, Sep 4, 2008 at 8:59 AM, Robert
Berman <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:bermanrl@embarqmail.com">bermanrl@embarqmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div bgcolor="#ffffff" text="#3333ff">
<div>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. <br>
<br>
I am currently attempting to work a challenge known as the 'Zeros of a
Factorial' challenge located at <a moz-do-not-send="true"
href="http://www.challenge-you.com/challenge?id=484" target="_blank">http://www.challenge-you.com/challenge?id=484</a>.
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?"<br>
<br>
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.<br>
<br>
Obviously, running a test on 1000000 would take some time and would not
even be close to the required number of trailing zeros. <br>
<br>
I need to know if I am even close with my approach to a workable
algorithm</div>
</div>
</blockquote>
<div>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.</div>
<div>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.</div>
<div> </div>
<blockquote class="gmail_quote"
style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div bgcolor="#ffffff" text="#3333ff">
<div> 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.</div>
</div>
</blockquote>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>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).</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>If any of my code doesn't make sense, let me know.</div>
<div>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.</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div> (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.)<br>
</div>
<div>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.)</div>
<div> </div>
</div>
</div>
</blockquote>
</body>
</html>