Tim Converse reports on recruiting trip to Michigan he made–that is, Michigan the University. He asked the audience trivia questions, including “how many trailing zeros in 100 factorial?”
I remember seeing 100! for the first time:
I wondered where all those (24) zeroes came from, but I never took the time to figure it out.
Nor did I have time to figure it out as I read Tim’s post, but I did have a couple of minutes to write a Lisp program to compute n! and count the zeros in 100!; this is essentially what I wrote:
(defun f (x) (if (= x 1) x (* x (f (1- x))))) (defun nz1 (x) (let ((str (princ-to-string (f x)))) (1- (- (length str) (position-if-not (lambda (ch) (char= ch #\0)) str :from-end t)))))
(nz1 (f 100)) -> 24
Well, this was good enough to answer Tim’s question, but he (rightly) took me to task for being so non-explanatory. So I spent some time looking at the problem, mainly by looking at the factorials from 1 to 100 and looking for patterns. Eventually I realized that it was the sum of how many times multiples of 5^1, 5^2, 5^3 … appeared. As a Lisp program:
(defun nz (x) (loop for i from 1 while (>= (expt 5 i) x) sum (floor x (expt 5 i))))
Essentially, these ‘pair up’ (as it were) with the 2s, 4s, 8s. … to produce the zero endings (eg 2*5, 12*15, …, 4*25).
I checked the wonderful On-Line Encyclopedia of Integer Sequences to see if this sequence appeared. At first, I couldn’t find it! Cool, I thought–I’ll have my own entry. Unfortunately for me, though, the sequence does appear, as sequence A027868 (I found this on a second search when I was looking to see if my entry had been accepted, Sorry to waste your time, N. J. A. Sloane). According to the MathWorld article on Factorial:
This is a special application of the general result first discovered by Legendre in 1808 that the largest power of a prime p dividing n! is … [formula omitted].
Nice to know I’m on the trailing edge of early 19th century number theory. I now promise myself a rest from Tim Converse and Joyce Park-related postings.
Interestingly, it’s a little difficult to search for 100! on both Yahoo Search and Google–and the Yahoo calculator doesn’t calculate factorial, and Google’s gives an approximation. But searching for “100 factorial is” on Yahoo and Google yields this page in Korean.