# 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)

-

1
– 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

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
````
-

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.

-

+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
````
-

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"]]
````
-
lang-mma
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9115663170814514, "perplexity_flag": "middle"}