# efficient way to count the number of zeros at the (right) end of a very large number

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?

(edit: the answer for the example should be 3082)

-
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. –  Ｊ. Ｍ. Feb 1 '12 at 3:12
@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. –  Isaac Feb 1 '12 at 3:15

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].

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

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

-
Welcome to Mathematica.se. From the looks of it, you've been using Mathematica for quite some time (or you learn very quickly)! –  David Carraher Oct 13 '12 at 0:57
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. –  Mr.Wizard Oct 13 '12 at 1:35
Alternatively: NumberOfFives[n_Integer] := Total[Quotient[n, 5^Range[IntegerLength[n, 5] - 1]]] –  Ｊ. Ｍ. Oct 24 '12 at 15:12
Exactly the same method I've come up during computation of million factorials using C. –  Mohsen Afshin Dec 23 '12 at 20:56

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.

-
+1 interesting... –  Rojo Feb 1 '12 at 17:44

First thing that comes to mind is something like

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


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

-
Right off, about twice as fast as my code and pretty elegant. –  Isaac Feb 1 '12 at 17:09

Specific to factorials:

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


3082

Or shorter:

Tr@Floor[# / 5^Range@Log[5, #]] & @ 12345

-
I'd have done Tr@Rest@NestWhileList[Quotient[#, 5] &, #, # > 1 &] &@12345 to implement de Polignac-Legendre myself... –  Ｊ. Ｍ. Feb 1 '12 at 4:25
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[]? –  Isaac Feb 1 '12 at 21:45
@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. –  Ｊ. Ｍ. Feb 1 '12 at 21:51
@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. –  Mr.Wizard Feb 1 '12 at 21:55
BTW @Isaac: for completeness, you could also try the version using FixedPointList[] instead of NestWhileList[]: Total[Rest[FixedPointList[Quotient[#, 5] &, 12345, SameTest -> (#1 <= 1 &)]]]. –  Ｊ. Ｍ. Feb 1 '12 at 21:58

Perhaps

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


Or, with regular expressions,

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

-