Finding Number of Trailing Zeros in Factorials
Date: 01/27/2005 at 13:16:05 From: Martin Subject: counting trailing zeros of factorials in any base system I noticed a way to compute the number of trailing zeros of a factorial in base 10 or 6 at your site. But that method doesn't work for me in base 4, 8, 16, etc. I think it is because the primes for those bases are the same, i.e. 2*2*2*2 for base 16. I noticed that some factorials in base ten have the same amount of zeros when in base 16, such as 10!. I've also tried to mess with exponents and use something like floor(n/x^i)+... where n is the factorial and i increases from 1 to y until floor is at least 1. For the starting x I tried the base 16 primes of 2, then 2*2, then 2*2*2, but none worked.
Date: 01/28/2005 at 18:06:32 From: Doctor Vogler Subject: Re: counting trailing zeros of factorials in any base system Hi Martin, Thanks for writing to Dr. Math. To count trailing zeros in any kind of number N in any base b, first you should factor your base (b) into products of prime powers. Then you should check how many times each prime in b divides the number N. Here is the part you are asking about: For each of those primes, divide the number of times it divides N by the exponent of the prime in b, and round down to the nearest integer. The smallest number you get (for all the primes) is the number of final zeros that N has in base b. Let's do an example. Suppose we want 700! in base 120. First we factorize 120: 120 = 2^3 * 3 * 5. Now we count how many times 2 goes into 700!. By the techniques from Trailing Zeros and Zero Factorial http://mathforum.org/library/drmath/view/55844.html and other places in our archives, which you surely already read, the number is [700/2] + [700/4] + [700/8] + ... + [700/256] + [700/512] = 350 + 175 + 87 + 43 + 21 + 10 + 5 + 2 + 1 = 694. Then we divide that by the exponent of 2 in 120, which is 3 (2^3 divides 120), 694/3 = 231.33, which rounds down to 231. Now we do the same for 3 and 5. Of course, since this is a factorial, we know the number of times 3 divides 700! will be at least as big as the number of times 5 divides 700! (although since we had to divide the 2s by 3, we still needed to check those). Then 5 goes into 700! [700/5] + [700/25] + [700/125] + [700/625] = 140 + 28 + 5 + 1 = 174. And 174 is smaller than 231, so there will be 174 trailing zeros in base 120. Similarly, there will be 231 trailing zeros in base 8, and 694 trailing zeros in base 2, and [694/4] = 173 trailing zeros in base 16 (hexadecimal). If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 01/29/2005 at 03:33:45 From: Martin Subject: Thank you (counting trailing zeros of factorials in any base system) Thanks, it works now! 8)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.