Trailing Zeros of Factorials
Trailing Zeros of Factorials
In the seventies when I got my first TI pocket calculator in school I developed a certain fascination for the factorial function. It was basically the most dangerous function around because if you entered any integer larger than 69 it would blow up with an error because it could not calculate numbers with more than two digits in the base-10 exponent and for most of them it could of course only show the first few most significant digits.
So it took me almost 40 years and the mind-boggling capacity of WL to handle arbitrary-sized integers (well almost) to ask the following question: What is the number of trailing zeros in n factorial? As a short reminder n! is the mathematical notation for the product of all positive integers less or equal to n.
As you can easily see from an example there are plenty of trailing zeros in the factorial of reasonably-sized integers:
So it took me almost 40 years and the mind-boggling capacity of WL to handle arbitrary-sized integers (well almost) to ask the following question: What is the number of trailing zeros in n factorial? As a short reminder n! is the mathematical notation for the product of all positive integers less or equal to n.
As you can easily see from an example there are plenty of trailing zeros in the factorial of reasonably-sized integers:
In[]:=
100!
Out[]=
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Well to answer the question above we reformulate it as the number of sought zeros is equal to how many times n factorial can be divided (meaning integer division) by ten without getting a remainder. But for getting a factor of 10 there needs to be a corresponding factor of 5 and one factor of 2 in the prime factorization of n factorial. Since every other number contains at least a factor of 2 in its prime factorization we can safely count only the factors of 5 in the factorization of the first n integers so we get a first (very functional and “pattern matchy” way to calculate the trailing zero function TZF:
In[]:=
TZF1[n_]:=Flatten[FactorInteger[Range[n]],1]//Cases[{5,a_}a]//Total
In[]:=
ListPlot[Table[TZF1[n],{n,100}],JoinedTrue,ImageSizeLarge,PlotRangeAll]
Out[]=
Well it looks pretty step-like with regular intervals so let’s plot the differences:
In[]:=
ListPlot[Differences[Table[TZF1[n],{n,100}]],JoinedTrue,ImageSizeLarge,PlotRangeAll]
Out[]=
Aha! For each we get i new trailing zeros, but that is then equal to just summing the integer quotients of dividing n by increasing powers of . So we have another candidate for the trailing zeros which definitely looks much more procedural:
i
5
i
5
In[]:=
TZF2[n_]:=Module[{i=1,result=0},While[<=n,result+=Quotient[n,];i++];result]
i
5
i
5
And finally we might always have done a mistake so let’s just see how long the last group of digits is for any n larger than 4, which is the brute force way to get the answer:
In[]:=
TZF3[n_]:=If[n<5,0,IntegerDigits[Factorial[n]]//SplitBy[#,1]&//Part[#,-1]&//Length]
In[]:=
m=150;ListPlot[{Table[TZF1[n],{n,m}],Table[TZF2[n],{n,m}],Table[TZF3[n],{n,m}]},JoinedTrue,ImageSizeLarge,PlotRangeAll]
Out[]=
All well it seems, of course not everything worked out right at first trial, but now that all three seem to coincide, it seems pretty watertight right?
So then let’s see which form might be most efficient to calculate the TZF function:
So then let’s see which form might be most efficient to calculate the TZF function:
In[]:=
n=10000;Timing[TZF1[n]]Timing[TZF2[n]]Timing[TZF3[n]]
Out[]=
{0.041059,2499}
Out[]=
{0.000055,2499}
Out[]=
{0.043205,2499}
So you see functional is not always faster unfortunately, but it is also surprising to see that taking the long detour to calculate the whole factorial does equally well roughly as the first variant which only factorizes rather small numbers.
But back to the original question we can see that we answer the original question pretty accurately by calculating the TZF function divided by n as a geometric sum:
But back to the original question we can see that we answer the original question pretty accurately by calculating the TZF function divided by n as a geometric sum:
In[]:=
n=.;Sum[1/5^i,{i,1,∞}]
Out[]=
1
4
So the trailing number of zeros of n factorial is approximately n/4 for large n (to be more accurate take one less). So if you get the question at the next party “how many trailing zeros are there in 10000 factorial?” just say “2499 of course”!
So what about other radices (plural for radix or base of the integer digit representation)? To find an the answer we have to consider the prime factorization of the radix which then of course can have more (or less) than two prime factors and each with a separate multiplicity to form the radix as a product. So for each of these prime factors of the radix we then have to calculate how many times p appears in the positive integer numbers smaller or equal to n and find the integer quotient when dividing by k. The smallest of these is then our trailing zeros count.
k
p
Let’s see if these agree to iron out obvious mistakes by feeding random samples. But beware, the factorial is still dangerous and will exhaust your physical memory if you throw in too big numbers or too small radices.
In order to get asymptotic values of the trailing zeros you now need to divide n by (p-1) k. You have to do this only with the prime factor that results in the largest value of (p-1) k of course. Then you round down again and you will be mostly very accurate. So let’s do an example: