Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this community
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.)
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].
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
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$
Oct 13, 2012 at 1:35
NumberOfFives[n_Integer] := Total[Quotient[n, 5^Range[IntegerLength[n, 5] - 1]]]
$\endgroup$
Oct 24, 2012 at 15:12
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 ---
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
Specific to factorials:
Tr@Floor@NestWhileList[#/5` &, #/5`, # > 1 &] & @ 12345
3082
Or shorter:
Tr@Floor[# / 5`^Range@Log[5, #]] & @ 12345
Tr@Rest@NestWhileList[Quotient[#, 5] &, #, # > 1 &] &@12345 to implement de Polignac-Legendre myself...
$\endgroup$
Feb 1, 2012 at 4:25
Tr[] as opposed to Total[]?
$\endgroup$
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$
Feb 1, 2012 at 21:51
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$
Feb 1, 2012 at 21:55
FixedPointList[] instead of NestWhileList[]: Total[Rest[FixedPointList[Quotient[#, 5] &, 12345, SameTest -> (#1 <= 1 &)]]].
$\endgroup$
Feb 1, 2012 at 21:58
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"]]
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.
