count zeros in a number

[dimitris]

Hello.

Consider e.g. the number 24^24*55^55.
This number ends with exactly 55 zeros as the following demonstrate

In[201]:= Mod[24^24*55^55, 10^55]
Mod[24^24*55^55, 10^56]

Out[201]= 0
Out[202]= 20000000000000000000000000000000000000000000000000000000


What I want now is a way to count the zeros that a number ends without
knowing in advance this number of zeros like in the above example.

Thanks in advance.
Dimitris

[DC]

Try

Last[Split[IntegerDigits[24^24*55^55]]]

[DrMajorBob]

n = 24^24*55^55

6998705566601499878519159087153235987310926417579055430641039765858300\
72320000000000000000000000000000000000000000000000000000000

IntegerDigits[n] /. {__, zeroes : 0 ..} :> Length@{zeroes}

55

The more complicated version:

IntegerDigits[n] /. {__, zeroes : Longest[0 ..]} :> Length@{zeroes}

55

isn't necessary, because __ is taken to mean Shortest[__] by default.

Bobby

--
DrMaj...@yahoo.com

[Andrzej Kozlowski]

On 2 Oct 2011, at 08:36, dimitris wrote:

> Hello.
>
> Consider e.g. the number 24^24*55^55.
> This number ends with exactly 55 zeros as the following demonstrate
>
> In[201]:= Mod[24^24*55^55, 10^55]
> Mod[24^24*55^55, 10^56]
>
> Out[201]= 0
> Out[202]= 20000000000000000000000000000000000000000000000000000000
>
>
> What I want now is a way to count the zeros that a number ends without
> knowing in advance this number of zeros like in the above example.
>
> Thanks in advance.
> Dimitris
>

Probably the most obvious way is to let Mathematica multiply out the numbers and count the trailing zeros, eg.

Length[Last[Split[IntegerDigits[24^24*55^55]]]]

55


An alternative approach is to just count the exponents of 5 and 2 and take the smaller one:

Min[
Cases[FactorInteger[24^24*55^55], {2, x_} | {5, y_} :> {x, y}]]

55

Andrzej Kozlowski

[Andrzej Kozlowski]

[Mark Adler]

Min[IntegerExponent[#, 2], IntegerExponent[#, 5]] &[24^24*55^55]
55

[Ulrich Arndt]

one way is to convert the number to a string and count the "0" at the end

a = 24^24*55^55
StringLength[
StringCases[ToString[a],
Longest[x : "0" ... ~~ EndOfString] -> x]][[1]]
a = 123
StringLength[
StringCases[ToString[a],
Longest[x : "0" ... ~~ EndOfString] -> x]][[1]]
a = 1230
StringLength[
StringCases[ToString[a],
Longest[x : "0" ... ~~ EndOfString] -> x]][[1]]

Ulrich

[Bill Rowe]

On 10/2/11 at 2:36 AM, dimm...@yahoo.com (dimitris) wrote:

>Consider e.g. the number 24^24*55^55. This number ends with exactly
>55 zeros as the following demonstrate

>In[201]:= Mod[24^24*55^55, 10^55] Mod[24^24*55^55, 10^56]

>Out[201]= 0 Out[202]=
>20000000000000000000000000000000000000000000000000000000

>What I want now is a way to count the zeros that a number ends
>without knowing in advance this number of zeros like in the above
>example.

Here are a couple of ways:

In[10]:= Count[IntegerDigits[Mod[24^24*55^55, 10^56]], 0]

Out[10]= 55

In[11]:= Length[Split[IntegerDigits[Mod[24^24*55^55, 10^56]]][[-1]]]

Out[11]= 55

The first method assumes the only zeros are trailing zeros. The
second does not make this assumption by does assume there are
trailing zeros.

[Peter Pein]

Using pattern matching makes this an easy one :-)

In[1]:= TrailingZeros[n_Integer] :=
IntegerDigits[n] /. {___, Except[0], z: ((0) ...)} :> Length[{z}]

TrailingZeros[24^24 55^55]
Out[2]= 55

[Peter Breitfeld]

dimitris wrote:

I would convert to a string and use a regular expression:

trailingZeros[n_] :=
StringLength@StringCases[ToString[n], RegularExpression["0+$"]]

trailingZeros[24^24 55^55]
Out={55}

trailingZeros[10000!]
Out={2499}

--
_________________________________________________________________
Peter Breitfeld, Bad Saulgau, Germany -- http://www.pBreitfeld.de

[Gabriel Landi]

num = Mod[24^24*55^55, 10^56];
Count[IntegerDigits@num, 0]

This is the simplest way I found.

[Harvey P. Dale]

=09
zeroes[n_]:=Module[{idn=IntegerDigits[n]},If[Last[idn]==0,Length[Split[i
dn][[-1]]],0]]
zeroes[24^24 55^55]

Best,

Harvey

[Dr. Wolfgang Hintze]

"dimitris" <dimm...@yahoo.com> schrieb im Newsbeitrag
news:j69104$rda$1...@smc.vnet.net...

You can use the function

f[z_]:=Length[Split[IntegerDigits[z]][[-1]]]
z = 24^24*55^55;
f[z]
62

Wolfgang

[Stefan Salanski]

All these solutions are very interesting, and they all work, but I
believe the simplest solution is actually a built in function,
specifically: IntegerExponent[].
IntegerExponent[n,b] returns the highest power of b which divides n,
which for b=10, is the number of trailing zeroes of n.
moreover, the default value of b is already 10, so that
IntegerExponent[n] gives the number of trailing zeroes of n.
In[1]:= IntegerExponent[24^24*55^55]
Out[1]= 55
http://reference.wolfram.com/mathematica/ref/IntegerExponent.html

-Stefan Salanski

[DrMajorBob]

But the answer is 55, not 62.

z = 24^24*55^55;
Length[Split[IntegerDigits[z]][[-1]]]

55

Bobby

On Mon, 03 Oct 2011 03:22:37 -0500, Dr. Wolfgang Hintze <w...@snafu.de>
wrote:

>
> "dimitris" <dimm...@yahoo.com> schrieb im Newsbeitrag
> news:j69104$rda$1...@smc.vnet.net...

> You can use the function
>
> f[z_]:=Length[Split[IntegerDigits[z]][[-1]]]
> z = 24^24*55^55;
> f[z]
> 62
>
> Wolfgang
>
>

--
DrMaj...@yahoo.com

[dimitris]

Thanks a lot to everyone that replied.

Dimitris

[Richard Fateman]

How disappointing that the usual crew did not come up with a way of
solving this simply, arithmetically, like this:

(n = 0; While[GCD[24^24*55^55, 10^n] == 10^n, n++]; n - 1)

or

(n = 0; x = 24^24*55^55;
While[Mod[x, 10] == 0, (x = x/10; n++) ]; n)

or any of the numerous minor variants....

but instead resorted to conversion to strings or factoring.

The arithmentic methods may be slower since they rely on the slow
implementation of looping constructs in Mathematica, but they
don't require any of the more esoteric features like
Exponents, Split, IntegerDigits, ...

RJF

[DrMajorBob]

There's nothing "esoteric" about IntegerDigits, Replace, or Repeated, as
in:

x = 24^24*55^55;
Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
Length@{zeroes}] // Timing

{0.000185, 55}

If we wanted brute-force arithmetic, we might use Fortran.

Your suggested solutions are NOT greatly hindered by "the slow
implementation of looping constructs in Mathematica", on the other hand:

(n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing

{0.000029, 0}

(n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing

{0.000018, 0}

Bobby

--
DrMaj...@yahoo.com

[Richard Fateman]

On 10/4/2011 9:44 AM, DrMajorBob wrote:
> There's nothing "esoteric" about IntegerDigits, Replace, or Repeated,
> as in:
>
> x = 24^24*55^55;
> Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
> Length@{zeroes}] // Timing
>
> {0.000185, 55}

My feeling is that these ARE esoteric. A person just introduced to
Mathematica would probably not encounter IntegerDigits, Repeated, or
patterns other than the trivial one used in pseudo function definitions as
f[x_]:= x+1.

>
> If we wanted brute-force arithmetic, we might use Fortran.
>
> Your suggested solutions are NOT greatly hindered by "the slow
> implementation of looping constructs in Mathematica", on the other hand:
>
> (n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing
>
> {0.000029, 0}

huh? I got {0., 55}. Perhaps my computer is faster or has a lower
resolution timer, but we should both get 55.

>
> (n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing
>
> {0.000018, 0}

I mention the slow implementation of looping constructs simply to warn
people that if you can resolve your computation by simple composition of
built-in functions e.g. F[G[H[x]]] and don't rely on Mathematica
to efficiently execute loops written as While[] For[] etc, you are
probably going to run faster. Let Mathematica's operation on compound
objects like lists do the job. Length[] is a lot faster than counting
with a While etc.

In my timings, doing the operations 1000 times..
Do[.....,{1000}]//Timing

I found that my solutions were about 10X faster than the IntegerDigits
one, on this particular value of x.

Fortran can't be used unless you manage arbitrary precision integers...

RJF

[DrMajorBob]

A person just introduced to Mathematica is NOT, as yet, a Mathematica
programmer.

Bobby

--
DrMaj...@yahoo.com

[DrMajorBob]

I'm guessing that I got zero because I ran some of the code with an
undefined x. My bad!

Correcting that, I find the esoteric method faster than your ancient,
outmoded ones:

x = 24^24*55^55;
Replace[IntegerDigits@x, {__, zeroes : 0 ..} :>
Length@{zeroes}] // Timing

{0.000198, 55}

(n = 0; While[GCD[x, 10^n] == 10^n, n++]; n - 1) // Timing

{0.000417, 55}

(n = 0; While[Mod[x, 10] == 0, (x = x/10; n++)]; n) // Timing

{0.000228, 55}

[Richard Fateman]

On 10/4/2011 2:33 PM, DrMajorBob wrote:
> I'm guessing that I got zero because I ran some of the code with an
> undefined x. My bad!

I think that you (me too) might not have noticed that one of my methods
changed x. Here is a safer version.

savedx= 24^24*55^55;


Well, here's another method..

(xs = ToString[savedx];
StringLength[xs] -
StringLength[ToString[ToExpression[StringReverse[xs]]]])

Let's time it, running 1000 times.

Do[ (xs = ToString[savedx];
StringLength[xs] -
StringLength[
ToString[ToExpression[StringReverse[xs]]]]), {1000}] // Timing

{0.063,Null}

This bizarre hack is reasonably fast, indeed twice as fast as your
method, on my system.

Do[Replace[

IntegerDigits@x, {__, zeroes : 0 ..} :>

Length@{zeroes}], {1000}] // Timing

{0.141, Null}

and seven times as fast as my older simple arithmetic method which uses
iteration,


Do[(n = 0; x = savedx; While[Mod[x, 10] == 0, (x = x/10; n++)];
n), {1000}] // Timing

{0.438, Null}

and which (as I contended) was inefficient in Mathematica. While you
seem to think that this method is ancient and outmoded, I think it is
not the method, but the implementation of iteration. Or perhaps of
arithmetic?

Another implementation of this arithmetical method on the same computer
takes 0.063 seconds.

RJF

[DrMajorBob]

This does the same thing as your code, essentially:

x = 24^24*55^55;
xd = IntegerDigits@x;
Length@xd - Length@IntegerDigits@FromDigits@Reverse@xd

55

and there's no reason for ToString to be faster than IntegerDigits, so...

Do[xd = IntegerDigits@x;
Length@xd -
Length@IntegerDigits@FromDigits@Reverse@xd, {1000}] // Timing

{0.029022, Null}

versus

Do[(xs = ToString[x];

StringLength[xs] -
StringLength[
ToString[ToExpression[StringReverse[xs]]]]), {1000}] // Timing

{0.032321, Null}

Bobby

On Tue, 04 Oct 2011 17:19:44 -0500, Richard Fateman

--
DrMaj...@yahoo.com

[Richard Fateman]

On 10/3/2011 10:34 PM, Stefan Salanski wrote:

>
> All these solutions are very interesting, and they all work, but I
> believe the simplest solution is actually a built in function,
> specifically: IntegerExponent[].
> IntegerExponent[n,b] returns the highest power of b which divides n,
> which for b=10, is the number of trailing zeroes of n.
>

why yes, all you need is one esoteric function.
Proof that it is esoteric? All the previous posters (me too) were
unaware of it. And presumably all the people who read the question and
did not post anything ...


The first example in the documentation illustrates exactly this usage.

RJF

[DrMajorBob]

It would be silly for Stefan not to mention IntegerExponent because it is
"esoteric", when he instantly makes it LESS esoteric by showing it to us.

Bobby

On Wed, 05 Oct 2011 03:03:18 -0500, Richard Fateman
<fat...@cs.berkeley.edu> wrote:

> On 10/3/2011 10:34 PM, Stefan Salanski wrote:
>
>>

>> All these solutions are very interesting, and they all work, but I
>> believe the simplest solution is actually a built in function,
>> specifically: IntegerExponent[].
>> IntegerExponent[n,b] returns the highest power of b which divides n,
>> which for b=10, is the number of trailing zeroes of n.
>>

> why yes, all you need is one esoteric function.
> Proof that it is esoteric? All the previous posters (me too) were
> unaware of it. And presumably all the people who read the question and
> did not post anything ...
>
>
> The first example in the documentation illustrates exactly this usage.
>
> RJF
>
>

--
DrMaj...@yahoo.com

[Dr. Wolfgang Hintze]

What about setting up a regular column "esoteric of the week" naming
functions that are rarely used ?

I would start with

Clip[x]

which I (shame on me) didn't know until this evening. Did you?

Wolfgang



"Richard Fateman" <fat...@cs.berkeley.edu> schrieb im Newsbeitrag
news:j6h3kn$74t$1...@smc.vnet.net...

[Mark Adler]

On 2011-10-05 01:14:15 -0700, Richard Fateman said:
> Proof that it is esoteric? All the previous posters (me too) were
> unaware of it.

I posted its use about five replies in.

However for some reason I only considered its use with prime numbers to
get the exponent of that prime in the integer's factorization (a sort
of selective FactorInteger). So my solution used the function twice
(on 2 and 5) when it didn't have to.

Mark