## Number of zeores and digits in N Factorial in Base B

**Question : What is the number of trailing zeroes and the number of digits in N factorial in Base B.**

For example,

20! can be written as 2432902008176640000 in decimal number system while it is equal to “207033167620255000000” in octal number system and “21C3677C82B40000” in hexadecimal number system. That means that 10 factorial has 4 trailing zeroes in Base 10 while it has 6 trailing zeroes in Base 8 and 4 trailing zeroes in Base 16. Also 10 factorial has 19 digits in Base 10 while it has 21 digits in Base 8 and 16 digits in Base 16. Now the question remains how to find it?

Now we can break the Base B as a product of primes :

B = *a ^{p1}* *

*b**

^{p2}*c** …

^{p3}Then the number of trailing zeroes in N factorial in Base B is given by the formulae

min{1/p1(n/a + n/(a*a) + ….), 1/p2(n/b + n/(b*b) + ..), ….}.

And the number of digits in N factorial is :

floor (ln(n!)/ln(B) + 1)

Here’s a sample C++ code :

#include<iostream> using namespace std; #include<math.h> int main() { int N,B,i,j,p,c,noz,k; while (scanf("%d%d",&N,&B)!=EOF) { noz=N; j=B; for (i=2;i<=B;i++) { if (j%i==0) { p=0; while (j%i==0) { p++; j/=i; } c=0; k=N; while (k/i>0) { c+=k/i; k/=i; } noz=min(noz,c/p); } } double ans=0; for (i=1;i<=N;i++) { ans+=log(i); } ans/=log(B);ans+=1.0; ans=floor(ans); printf("%d %.0lf\n",noz,ans); } }

NJOY!

-fR0DDY

hey u seem to have a good knowledge of number theory.let me know some references (particularly useful for coding)

shivJanuary 15, 2011 at 12:20 AM

N=33, B=45;

45 = 3^2 * 5;

33! = ……3^15 * 5^7………..

zero = min(33, 15/2) = 7; //for 3

zero = min(7, 7/1) = 7; //for 7

so trailing zero = 7

your algo is trailing zero = min(zero, number of factor in factorial / number of factor in base);

would you please explain it mathematically.

HasanJuly 21, 2012 at 8:52 PM