# COME ON CODE ON

A blog about programming and more programming.

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

with 2 comments

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 = ap1 * bp2 * cp3 * …
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

Advertisements

Written by fR0DDY

February 17, 2010 at 5:47 PM

Posted in Maths, Programming

Tagged with , , , , , ,

### 2 Responses

Subscribe to comments with RSS.

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

January 15, 2011 at 12:20 AM

2. 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. Hasan

July 21, 2012 at 8:52 PM