Message Boards Message Boards

GROUPS:

Counting Trailing Zeros Of Factorials

Posted 3 months ago
1428 Views
|
13 Replies
|
12 Total Likes
|

Introduction

You may have noticed that the factorial function for integers generates a lot of trailing zeros at the end e.g. 100! evaluates to

9332621544394415268169923885626670049071596826438162146859296389521759\
9993229915608941463976156518286253697920827223758251185210916864000000\
000000000000000000

That's 24 zeros right there. Maybe you would like to figure out how to calculate the exact number for arbitrary input integers? And then maybe for any chosen radix as well i.e. not using the decimal representation? I don't want to spoil the fun for you, so please go chew away at this nice little mathematical diversion. The asymptotic "TZF" function for large integers is really compute-friendly, so for "easy" large integers you will be able to do the algebra just using a simple rule.

Well and then it is always possible I have made a mistake, so I include my notebook on this problem for you to compare.

Have fun!

enter image description here

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:

100!

9332621544394415268169923885626670049071596826438162146859296389521759\ 9993229915608941463976156518286253697920827223758251185210916864000000\ 000000000000000000

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:

TZF1[n_] := 
 Flatten[FactorInteger[Range[n]] , 1] // Cases[{5, a_} -> a] // Total

ListPlot[Table[TZF1[n], {n, 100}], Joined -> True, ImageSize -> Large,
  PlotRange -> All]

enter image description here

Well it looks pretty step-like with regular intervals so let's plot the differences:

ListPlot[Differences[Table[TZF1[n], {n, 100}]], Joined -> True, 
 ImageSize -> Large, PlotRange -> All]

enter image description here

Aha! For each $5^i$ we get i new trailing zeros, but that is then equal to just summing the integer quotients of dividing n by increasing powers of $5^i$. So we have another candidate for the trailing zeros which definitely looks much more procedural:

TZF2[n_] := Module[{i = 1, result = 0},  While[5^i <= n, result += Quotient[n, 5^i]; i++]; result]

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:

TZF3[n_] :=  If[n < 5, 0,  IntegerDigits[Factorial[n]] // SplitBy[#, 1] & // Part[#, -1] & //  Length]

m = 150; ListPlot[{Table[TZF1[n], {n, m}], Table[TZF2[n], {n, m}], 
  Table[TZF3[n], {n, m}]}, Joined -> True, ImageSize -> Large,  PlotRange -> All]

enter image description here

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:

n = 10000;
Timing[TZF1[n]]
Timing[TZF2[n]]
Timing[TZF3[n]]

{0.041059, 2499} 
{0.000055, 2499}
{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:

n =.;
Sum[1/5^i, {i, 1, \[Infinity]}]

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 $p^k$ 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.

TZF4[n_, r_] := Quotient[Total[ Cases[Flatten[FactorInteger[Range[n]] , 1] , {#[[1]], a_} -> 
        a]], #[[2]]] & /@ FactorInteger[r] // Min

TZF5[n_, r_] := 
 Module[{f = FactorInteger[r], q = Table[0, Length[FactorInteger[r]]],
    i, p, q0},
  Do[i = 1; p = f[[j, 1]]; q0 = 0;
   While[p^i <= n, q0 += Quotient[n, p^i]; i++];
   q[[j]] = q0
   , {j, Length[f]}];
  If[Min[q] > 0, Min[Quotient[q, f[[;; , 2]]]], 0]
  ]

TZF6[n_, r_] := 
 IntegerDigits[Factorial[n], r] // SplitBy[#, 1] & // 
  If[Part[#, -1][[1]] == 0, Length[Part[#, -1]], 0] &

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.

Table[{n = RandomInteger[10000], r = RandomInteger[{5, 30}], 
   TZF4[n, r], TZF5[n, r], TZF6[n, r]}, 10] // TableForm

enter image description here

Table[{n = RandomInteger[10000], TZF1[n], TZF2[n], TZF3[n], 
   TZF4[n, 10], TZF5[n, 10], TZF6[n, 10]}, 10] // TableForm

enter image description here

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:

TZF5[10000, 72]

2498

For radix 72 the prime decomposition is $2^3 3^2$, so again it's a division by four (from the first factor) but now we'd actually would have to subtract 2 to get the right number. If you end up with a tricky radix decomposition for the party trick you might actually have to consult the pocket calculator on your smartphone for the division. To close out I have to confess that I still own a working HP-15C, an icon of computation devices and a testament to solid engineering:

Well I am looking forward to the day when we are going to have hardware that durable again and being able to run WL from it.

If you liked this piece and want to explore further, why not generalizing the TZF functions above to mixed radix representations or make your own variant of them to optimize code, memory or performance.

enter image description here

13 Replies

Very useful for this problem:

https://projecteuler.net/problem=160

I had already solved it though ;-)

This is awesome! Thank you so much for sharing. By the way, we have this newly launched Wolfram Function Repository which could be a great place for your cool TZF :-)

Thanks for the cred Vitaly, I have now submitted a version of TZF5 with some argument checks to the function repo. Great way to share user functions with familiar documentation format.

Hi, I believe that is accomplished by the Wolfram team, in the beginning I only had some intro text and the notebook. So the credit goes to them.

Posted 1 month ago

Here is my Function I use to calculate the number of trailing zeros of a Factorial, It doesn't actually calculate any factorials so is quick for very large factorials i.e. 10^100!

Ntz[m_] := Total[Table[Floor[m/5^n], {n, 1, Floor[Log[m]/Log[5]]}]]

enter image description here - Congratulations! This post is now featured in our Staff Pick column as distinguished by a badge on your profile of a Featured Contributor! Thank you, keep it coming, and consider contributing your work to the The Notebook Archive!

Posted 2 months ago

Very nice. I'm impressed by how the post mirrors your NB. Is there an easy (automatic) way to upload all the cells from a NB?

Posted 2 months ago

Thank you. They're hired! I've been working on a comment but managing cells and formats is a task for these fingers. Being thorough is punished IMHO. Of all blogs this is the one that should support Mathematical documentation.

  • Later

As it often happens there is a very concise form for this calculation with built-in Wolfram functions: IntegerExponent[Factorial[n], b] but the optimised version in the notebook is considerably faster for large integers. I have however problems on submitting the fast version to the Function Repository. Check, preview and deploy work fine but when submitting I get "ResourceSubmit::apierr The parameter FunctionLocation is missing."

Posted 1 month ago

If you liked this piece and want to explore further, why not generalizing the TZF functions above to mixed radix representations or make your own variant of them to optimize code, memory or performance.

Done. I substituted recursion for table accumulation. There are three functions,one (stack) specialized for base 10 (prime=5), another (stack) for any prime radix, and the ultimate (tzf) to handle the mixed radii - modeled after your TZF5. I removed the test for min>0 since 0 divided by power is still 0.

stack[0] := 0;
stack[n_] := Quotient[n, 5] + stack[Quotient[n, 5]];

stack[0, r_] := 0;
stack[n_, r_] := Quotient[n, r] + stack[Quotient[n, r], r];

 tzf[n_, r_] := 
  Min[Quotient[stack[n, #[[1]]], #[[2]]] & /@ FactorInteger[r]];

The new functions are faster. Timing tests follow for TrailingZerosFactorial and the Ntz submission. TrailingZerosFactorial beats Ntz for very large values. The columns are the N of N!, time for function 1, time for function 2, verification that the values match, and finally the ratio of times.

testGrowth[TrailingZerosFactorial, tzf, 72, time -> 0.1, power -> 4, 
 size -> 10]

tests

enter image description here

To test Ntz I had to define a two-parameter version.

Ntz[m_] := Total[Table[Floor[m/5^n], {n, 1, Floor[Log[m]/Log[5]]}]]
Ntz[m_, r_] := Ntz[m];

Finally Ntz fails for any power of 5.

enter image description here

Test driver

testGrowth[p1_, p2_, radix_, 
  OptionsPattern[{time -> 0.2, power -> 8, size -> 10}]] := 
 Module[{n, n1, n2}, 
  Block[{$RecursionLimit = Infinity}, 
    Table[{(n = RandomInteger[10^2^i]) // 
       N, (n1 = 
         RepeatedTiming[p1[n, radix], OptionValue[time]])[[1]], (n2 = 
         RepeatedTiming[p2[n, radix], OptionValue[time]])[[1]], 
      n1[[2]] == n2[[2]], n1[[1]]/n2[[1]]}, {i, OptionValue[power], 
      OptionValue[power] + OptionValue[size]}]] // TableForm]

Very concise indeed, and fast too!

Amazing, and really impressive how decently Wolfram handles calculations of Random numbers with 16384 digits!

Posted 1 month ago

Ntz aborts when the input is a power of 5.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract