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

Question

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)

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

Specific to factorials:

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

3082

Or shorter:

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

Answer 6

Perhaps

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

Or, with regular expressions,

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