Problem with exponent of p in n! algorithm (was: a(27) new higher lower bound)
David Wilson
davidwwilson at comcast.net
Wed Nov 23 00:36:20 CET 2005
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
>
More information about the SeqFan
mailing list