Well, Wilson's Theorem Jr. is out the window. And of course, Bell pseudoprime is infinitely preferable to Wilson pseudoprime. So I remain in obscurity. At least I've discovered a primality test that is at once computationally difficult and unreliable. Would you be the discoverer of the first Bell pseudoprime, [MD]r. Lunnon? ----- Original Message ----- From: "Fred lunnon" <fred.lunnon@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Saturday, July 21, 2007 12:32 AM Subject: Re: [math-fun] Bell number question
On 7/16/07, David Wilson <davidwwilson@comcast.net> wrote:
It looks as if B(p) == 2 (mod p) for prime p.
Besides the Touchard recurrence argument, it is well-known that
B(n) = \sum_i S(n, i)
where S(n, i) denotes second-kind Stirling numbers; and it can be shown (using a refinement of the Dobinski sum mentioned below) that for prime p,
S(p, i) mod p = 0 unless i = 1,p, when S(p, i) = 1.
Is this true, and are there "Bell pseudoprimes" in this respect?
Yes indeed: in order of smallest factor, the first example is
m = 21361 = 41*521
Verifying that B(m) mod m = 2 for this value of m is not entirely trivial. However, by the Chinese remainder theorem the result is equivalent to
B(m) mod p = 2 for p | m;
furthermore, it is a theorem that for prime p and natural q, in umbral notation
B(p q) mod p = (B + 1)^q = B(q+1).
[See for example Lunnon,~W.~F.~&~Pleasants,~P.~A.~B.~&~Stephens,~N.~M. Arithmetic Properties of Bell Numbers to Composite Modulus I, Acta Arith 35, pp~1-16 (1979).]
Putting these together, we need only verify instead that
B(522) mod 41 = B(42) mod 521 = 2
which would easily be evaluated directly under Maple 9, using bell(n) from the combinat package.
But you can't stop progress: under Maple 10, bell(n) takes a stupendously long time to evaluate anything over n = 170 or so, despite its predecessor being easily good for n = 2500. Fortunately, a simple workaround via sums of Stirling numbers
with(combinat); p := 522; q := 41; add(stirling2(p, i), i = 0..p) mod q; add(stirling2(q, i), i = 0..q) mod p;
grinds to a conclusion in a minute (G4 Macintosh).
A much faster alternative --- unfortunately requiring rather delicate estimation of precision and convergence --- would be the Dobinski infinite sum
B(n) = (1/e) \sum_{i >= 0} n^i / i!
--- but even this will not easily cope with B(m) above directly.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- No virus found in this incoming message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.11/909 - Release Date: 7/20/2007 4:39 PM