27
$\begingroup$

If I want to count the number of zeros at the (right) end of a large number, like $12345!$, I can use something like:

Length[Last[Split[IntegerDigits[12345!]]]]

But this seems clumsy, since it's potentially doing the full work of Split[] to the whole list of digits when all I need is the length of the run of $0$s at the end of the list. Is there a more efficient (and particularly more Mathematica-elegant) way to do this?

(The answer for the example should be 3082.)

$\endgroup$
  • 3
    $\begingroup$ Interesting question; I'll only note (I believe you know this already, but I'm putting it out as a reminder) that one could use the de Polignac-Legendre formula to count the number of zeros at the end of a factorial. $\endgroup$ – J. M. will be back soon Feb 1 '12 at 3:12
  • 2
    $\begingroup$ @J.M.: Yeah, I was actually using Mathematica to check the results of applying that formula by hand and I wasn't happy with the Mathematica code that I came up with. $\endgroup$ – Isaac Feb 1 '12 at 3:15
32
$\begingroup$

For general large integers n, I don't know if there's a better method than Min[IntegerExponent[n, 5], IntegerExponent[n, 2]]. Or more compactly, IntegerExponent[n, 10] or IntegerExponent[n].

$\endgroup$
  • $\begingroup$ I liked yours better $\endgroup$ – Rojo Feb 1 '12 at 3:24
  • $\begingroup$ This is certainly more concise and "Mathematicaic" than what I'd cobbled together. It also seems to be 3-7 times faster. $\endgroup$ – Isaac Feb 1 '12 at 3:55
16
$\begingroup$

If you are strictly interested in the number of trailing zeros in factorials $n!$, as the example in your question suggests, then consider the number of pairs of 2 and 5 in all the factors of numbers 1 through $n$. There is always a 2 to match a 5, so the number of fives gives the number of zeros. Integers divisible by 5 contribute one 5 to the total. Integers divisible by 25 contribute one additional 5, and so on. The maximum power to consider is Floor[Log[5,n]].

This method avoids time- and memory-consuming calculation of $n!$, and is about 50 times faster than IntegerExponent on my machine.

NumberOfFives[n_Integer] := Total[Floor[n/5^Range[Floor[Log[5,n]]]]]

However, the fastest method I've found to calculate the exponent of prime $p$ in $n!$ is the following:

PrimeExponent[n_Integer, p_Integer] := (n - Total[IntegerDigits[n, p]])/(p - 1)

which, on my machine, is about three times as fast as Mr. Wizard's answer:

Tr@Floor@NestWhileList[#/5` &, #/5`, # > 1 &] & @ 12345
$\endgroup$
  • 1
    $\begingroup$ Welcome to Mathematica.se. From the looks of it, you've been using Mathematica for quite some time (or you learn very quickly)! $\endgroup$ – DavidC Oct 13 '12 at 0:57
  • 1
    $\begingroup$ As David said, welcome! You're selling this method short. With very large numbers my method loses precision and 5` needs to be changed to 5 to be accurate. With this, and a big number, e.g. RandomInteger[1*^5000], your code is about 700 times faster than mine. Nicely done. $\endgroup$ – Mr.Wizard Oct 13 '12 at 1:35
  • $\begingroup$ Alternatively: NumberOfFives[n_Integer] := Total[Quotient[n, 5^Range[IntegerLength[n, 5] - 1]]] $\endgroup$ – J. M. will be back soon Oct 24 '12 at 15:12
  • $\begingroup$ Exactly the same method I've come up during computation of million factorials using C. $\endgroup$ – Mohsen Afshin Dec 23 '12 at 20:56
10
$\begingroup$

Here is a recursive divide-and-conquer. There are probably nicer ways to code it.

trailingZeros[n_, b_] := Module[
  {scale=Log[b,N[n]], sqrt, ndigits},
  If [scale<1, Return[0]];
  sqrt = Ceiling[scale/2];
  ndigits = IntegerDigits[n, b^sqrt, 2];
  If [Last[ndigits]==0,
    sqrt + trailingZeros[First[ndigits],b],
    trailingZeros[Last[ndigits], b]]
  ]

In[39]:= Timing[trailingZeros[4234567!, 33]]
Out[39]= {6.740000, 423454}

In terms of speed, it is essentially identical to J.M.'s approach. It just shows how one might do this were there no IntegerExponent function available.

--- edit 2017-06-25 ---

Since this showed up again I decided to time the various responses, all special-cased to digits base 10. The second and fifth are also specialized for factorials and are, as noted in respective responses and comments, hugely faster than the rest. The input for them is the non-factorialed value while for the rest it is the factorial.

zero1[n_] := 
 StringCases[
  ToString[n], {Longest[x : "0" ..] ~~ EndOfString} :> StringLength@x]
zero2[n_] := Tr@Floor@NestWhileList[#/5` &, #/5`, # > 1 &] &@n
zero3[n_] := LengthWhile[Reverse@IntegerDigits[n], # == 0 &]
zero4[n_] := 
 Module[{scale = Log[10, N[n]], sqrt, ndigits}, 
  If[scale < 1, Return[0]];
  sqrt = Ceiling[scale/2];
  ndigits = IntegerDigits[n, 10^sqrt, 2];
  If[Last[ndigits] == 0, sqrt + zero4[First[ndigits]], 
   zero4[Last[ndigits]]]]
zero5[n_Integer] := (n - Total[IntegerDigits[n, 5]])/4
zero6[n_] := IntegerExponent[n, 10]

Here is a big test. It shows that the "slow" methods are all comparable though there are modest factors separating them: best to worst is around a factor of 4 with this test.

nn = 12345678;
mm = nn!;

AbsoluteTiming[zero1[mm]]
AbsoluteTiming[zero2[nn]]
AbsoluteTiming[zero3[mm]]
AbsoluteTiming[zero4[mm]]
AbsoluteTiming[zero5[nn]]
AbsoluteTiming[zero6[mm]]

(* Out[114]= {78.1305, {3086416}}

Out[115]= {0.0000988615, 3086416}

Out[116]= {95.3831, 3086416}

Out[117]= {22.2577, 3086416}

Out[118]= {0.0000522287, 3086416}

Out[119]= {45.3224, 3086416} *)

I was a bit surprised that IntegerExponent was not fastest and maybe more surprised that it is almost exactly a factor of 2 off in terms of speed. Something to look into on a rainy day.

--- end edit ---

$\endgroup$
8
$\begingroup$

First thing that comes to mind is something like

LengthWhile[Reverse @ IntegerDigits[12345!], # == 0 &]

Clearly a compiled version, procedural, must be faster but less Mathematica elegant

$\endgroup$
  • $\begingroup$ Right off, about twice as fast as my code and pretty elegant. $\endgroup$ – Isaac Feb 1 '12 at 17:09
5
$\begingroup$

Specific to factorials:

Tr@Floor@NestWhileList[#/5` &, #/5`, # > 1 &] & @ 12345

3082

Or shorter:

Tr@Floor[# / 5`^Range@Log[5, #]] & @ 12345
$\endgroup$
  • 4
    $\begingroup$ I'd have done Tr@Rest@NestWhileList[Quotient[#, 5] &, #, # > 1 &] &@12345 to implement de Polignac-Legendre myself... $\endgroup$ – J. M. will be back soon Feb 1 '12 at 4:25
  • $\begingroup$ The first one and @J.M.'s suggestion seem to be about equally fast; the second one seems to take about 5-10 times as long. Is there a reason to use Tr[] as opposed to Total[]? $\endgroup$ – Isaac Feb 1 '12 at 21:45
  • $\begingroup$ @Isaac: He just wants it short, methinks (and it does work). I prefer using Total[] myself for purposes of readability (and since a matrix trace isn't what's being computed here)... likely it's the flooring of the logarithm that slows things down in the second snippet. $\endgroup$ – J. M. will be back soon Feb 1 '12 at 21:51
  • $\begingroup$ @Isaac I use Tr most often. It is very fast on packed arrays. Also, I find both Tr and Total a little ambiguous, in that they are multipurpose functions; Plus @@ is clearer, but more characters and often slower. Each has its place. $\endgroup$ – Mr.Wizard Feb 1 '12 at 21:55
  • $\begingroup$ BTW @Isaac: for completeness, you could also try the version using FixedPointList[] instead of NestWhileList[]: Total[Rest[FixedPointList[Quotient[#, 5] &, 12345, SameTest -> (#1 <= 1 &)]]]. $\endgroup$ – J. M. will be back soon Feb 1 '12 at 21:58
3
$\begingroup$

Update:

Module[{id = IntegerDigits@#}, 
   Length[id] - Length[Internal`DeleteTrailingZeros@id]] &@(12345!)

3082

Original post:

Perhaps

 StringCases[ToString[12345!], {Longest[x : "0" ..] ~~ EndOfString} :> 
  StringLength@x]

Or, with regular expressions,

 StringCases[ToString[12345!], RegularExpression["(0+)$"] :> StringLength["$1"]]
$\endgroup$
0
$\begingroup$

For the number of terminal zeros in $n!$:

   f[n_Integer] := Sum[Floor[n/5^i], {i, Floor[Log[5, n]]}]

Timing[f[8340958340958304980670987203849750238475]]

(*

{0.000485, 2085239585239576245167746800962437559590}

*)

This ought to be fast enough for any reasonable application.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.