Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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)

share|improve this question
1  
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. –  J. M. Feb 1 '12 at 3:12
1  
@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

6 Answers 6

up vote 27 down vote accepted

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

share|improve this answer
    
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
share|improve this answer
1  
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
1  
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]]] –  J. M. 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.

share|improve this answer
    
+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

share|improve this answer
    
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
share|improve this answer
3  
I'd have done Tr@Rest@NestWhileList[Quotient[#, 5] &, #, # > 1 &] &@12345 to implement de Polignac-Legendre myself... –  J. M. 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. –  J. M. 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 &)]]]. –  J. M. 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"]]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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