Problem with exponent of p in n! algorithm (was: a(27) new higher lower bound)

[David Wilson]

No clue, don't know Mma

The first difference seems to be e(2, 4) where you get 2 instead of the expected 
3.

The way e(p, n) is computed is as follows:

[n/p] + [n/p^2] + [n/p^3] + ...

where the terms eventually become 0.

For example, e(2, 4) is

[4/2] + [4/4] + [4/8] + [4/16] + ...

= 2 + 1 + 0 + 0 + ...

= 3.

Each term t_k in this sum can be gotten as t_k = [t_(k-1)/p]

I don't know how to make Mathematica do this.

----- Original Message ----- 
From: "Alonso Del Arte" <alonso.delarte at gmail.com>
To: "David Wilson" <davidwwilson at comcast.net>; <seqfan at ext.jussieu.fr>
Sent: Tuesday, November 22, 2005 5:26 PM
Subject: Problem with exponent of p in n! algorithm (was: a(27) new higher lower 
bound)


> David, there is a problem with the algorithm
>
>   int e(int p, int n) {
>       int s = 0;
>       while (n > 0) {
>           n /= p;   // That is, n = floor(n/p)
>           s += n;
>       }
>       return s;
>   }
>
> I implemented in Mathematica thus:
>
> expoPF[p_, n_] := Module[{s, x}, x =
>   n; s = 0; While[x > 0; x = Floor[x/p]]; s = s + x; s]
>
> then gave the command
>
> Table[expoPF[2, n], {n, 25}]
>
> which gave the results {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7,
> 8, 8, 9, 9, 10, 10, 11, 11, 12, 12} (A004526, Integers repeated.)
>
> Instead I expected {0, 1, 1, 3, 3, 4, 4, 7, 7, 8, 8, 10, 10, 11, 11,
> 15, 15, 16, 16, 18, 18, 19, 19, 22, 22} (A011371, n minus (number of
> 1's in binary expansion of n). Also highest power of 2 dividing n!.).
>
> Alonso
>