Saturday, June 18, 2011

Calculating the Number of Trailing Zeros in a Factorial

The factorial function, denoted \( n! \), where \( n \in \mathbb{Z}^* \), is defined as follows: \[ n! = \begin{cases} 1 & \text{if $n = 0$,} \\ n(n - 1)! & \text{otherwise}. \end{cases} \] In the case of \( n = 10 \), \( 10! = 3\,628\,800 \). Note that that value has two trailing zeros. When \( n = 20 \), \( 20! = 2\,432\,902\,008\,176\,640\,000 \) and has four trailing zeros. Can we devise an algorithm to determine how many trailing zeroes there are in \( n! \) without calculating \( n! \)?

Let us define a function \( z : \mathbb{N} \to \mathbb{N} \) that accepts an argument \( n \) that yields the number of trailing zeros in \( n! \). So, using our two examples above, we know that \( z(10) = 2 \) and \( z(20) = 4 \). Now, what is \( z(100) \)?

An integer \( a \) has \( k \) trailing zeros iff \( a = b \cdot 10^k \) for some integer \( b \). Now, the prime factors of \( 10 \) are \( 2 \) and \( 5 \). So, what if we consider the prime factors of each factor in a factorial product? For example, consider the first six terms (after \( 1 \)) of \( 100! \) and their prime factors. We omit \( 1 \) because of its idempotence: \[ \begin{align} 2 &= 2 \\ 3 &= 3 \\ 4 &= 2^2 \\ 5 &= 5 \\ 6 &= 2 \cdot 3 \\ 7 &= 7 \end{align} \] We see that \( 7! \) contains one \( 5 \) and (more than) one \( 2 \). Therefore, \( 7! \) contains a factor of \( 10 \), so we should expect there to be one trailing zero in \( 7! \). And we see that \( 7! = 5040 \), which does indeed have one trailing zero. This suggests that we could, for any integer \( n \) in \( n! \), cycle through the integers from \( 2 \) to \( n \), finding the prime factorization of each integer, and counting pairs of \( 2 \) and \( 5 \) that we find.

You might have noticed from our example of \( 7! \) that there are four \( 2 \)s and only one \( 5 \). Consider that there are \( n/2 \) even factors in \( n! \)—that is, every other integer factor of \( n! \), starting at \(2\), is even. So there are \( n/2 \) even factors. Each of these has at least one \( 2 \) in its prime factorization, and many of them have more than one. Now consider how many factors of \( 5 \) there are in \( n! \): there are, in fact, \( n / 5 \). So, we can see that, for every \( 5 \) we find in \( n! \), there is a \( 2 \) we can match with it. This suggests that we only need count the \( 5 \)s and not the pairs of \( 2 \) and \( 5 \).

This now suggests an algorithm, presented here in Java:

Using this algorithm, we find that \( z(100) = 24 \).

5 comments:

sandeep saxena said...

I will appreciate your help once again. thanks in advance.
Drupal Training in Chennai
Drupal Course in Chennai
Drupal 8 Training
Photoshop Classes in Chennai
Photo Editing Courses in Chennai
Photoshop Training Institute in Chennai
Drupal Training in Tnagar
Drupal Training in Velachery

sheela rajesh said...

This blog is full of Innovative ideas.surely i will look into this insight.please add more information's like this soon.
Hadoop Training in Chennai
Big data training in chennai
big data training in velachery
JAVA Training in Chennai
Python Training in Chennai
SEO Training in Chennai
Hadoop training in chennai
Big data training in chennai
big data training in velachery

Manipriyan said...


Useful content. Thanks for Sharing. It shows your indepth knowledge on the subject. Pls keep updating.


AWS Training in Chennai
Blue Prism Training in Chennai

HOT AND SEXY INDEPENDENT ESCORTS IN LUCKNOW said...

THANK YOU FOR VISITING MY WEBSITE:-
russian escorts in gurgaon
housewife escorts in gurgaon
gurgaon escort services
gurgaon escorts
escorts in gurgaon
escort services in gurgaon
gurgaon call girls
call girls in gurgaon

Benjamin Jones said...

Our Cheap Escorts Service in Gujarat assure you to provide you heavenly expertise here in Ajmer solely.Dating Escorts in Gujarat Fulfilling your dreams is our aim and our attractive ladies are extremely dedicated to High Profile Call Girls in Agra succeed in their aim.Indore Housewife Escorts agency Our all Call Girls don’t seem to be solely incredibly lovely however are well versed in reading the mind and body of our purchasers.Haridwar Housewife Escorts agency They provide refreshing and totally different treatment to each shopper as Goa Housewife Escorts agency clients would like.

Post a Comment