How the heck did RWG come across it? WFL On 7/19/13, Bill Gosper < billgosper@gmail.com> wrote: What the heck use is A006005, "The odd prime numbers together with 1"? Claim: the presence of 1 and the absence of 2 suggest these are actually "Numbers 2n+1 such that 0=Mod[Binomial[2n,n]-(-1)^n,2n+1]" See Concrete Math (G,K&P) Exercise 5.110 I.e., A065091 ∪ A163209 ∪ {1}, suggesting that A163209 should really be *1,5907*, *1194649*, 12327121, "Catalan pseudoprimes: (odd) nonprime integers n=2*m+1 satisfying A000108< http://oeis.org/A000108>(m) == (-1)^m * 2 (mod n). " A176997, " Odd numbers n such that (2^(n-1) mod n) = (4^(n-1) mod n) = (8^(n-1) mod n)= .. = (k^(n-1) mod n) for k=2, 4, 8, .., smallest power of 2>n" should be extended through 341 to avoid matching A006005. (Is this not equivalent to "Numbers n such that 1 = (2^(n-1) mod n) = (4^(n-1) mod n) = (8^(n-1) mod n)= .. = (k^(n-1) mod n) for k=2, 4, 8, .., smallest power of 2>n "?) Likewise, 0, 1, 2, 3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33,... A102781 "Number of even numbers less than the n - th prime." is probably less useful than "Numbers n such that 0=Mod[Binomial[2n,n]-(-1)^n,2n+1]" which also include 2953, (1093^2 - 1)/2, and (3511^2 - 1)/2. --rwg See math-fun-archive-931123-950622.txt excerpt below. Anybody know how far the Catalan pseudoprime search has been pushed? E.g., past the Wieferich search? http://gradelle.educanet2.ch/christian.aebi/.ws_gen/9/catalan.pdf gives two stronger Catalan pseudoprime tests: 0 == Mod[(-1)^((p - 1)/2)* CatalanNumber[(p - 1)/2] - 2 (-1 + 2^p) (1 - p), p^2] 0 == Mod[(-1)^((p - 1)/2)*CatalanNumber[(p - 1)/2] - (1 - p + p^2)*2^(2*p - 1), p^3] AFAIK, *no* false positives are known! Can the sexy trick for computing binomial(n,k) mod p by looking at the carries when adding k to n-k in base p be turned into an efficient probable prime test? Can the trick be extended to mod p^2 and mod p^3 to facilitate the Catalans in the above identities? Failing that, how about just 0 == Mod[(-1)^((p - 1)/2)* CatalanNumber[(p - 1)/2] - 2^p , p] (after checking for 5907, 1093^2, and 3511^2)? --rwg Why doesn't Mma Binomial take a Modulus option? Macsyma has binomial_modulus. I forget if it can Chinese remainder for composite modulus.

From rwg@NEWTON.Macsyma.COM Wed May 31 01:11:00 1995 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 31 May 1995 01:20:23 MST Received: from newton.macsyma.com by optima.cs.arizona.edu (5.65c/15) via SMTP id AA24896; Wed, 31 May 1995 01:20:21 MST Received: from SWEATHOUSE.macsyma.com ([192.233.166.105]) by NEWTON.Macsyma.COM via INTERNET with SMTP id 320962; 31 May 1995 04:11:10-0400 Date: Wed, 31 May 1995 01:11-0700 From: Bill Gosper <rwg@NEWTON.macsyma.com> Subject: q-binom mod 1-q^p To: math-fun@cs.arizona.edu Cc: mrahman@math.carleton.ca, george@math.nwu.edu, askey@math.wisc.edu, math-fun@cs.arizona.edu Message-Id: <19950531081123.8.RWG@SWEATHOUSE.macsyma.com>

n Recall that ( ) mod p can [be] very quickly found from the carries when adding k k to n-k in base p, when p is a prime. (In fact, doing this for several p and then Chinese remaindering is a good way to compute binomial coeffs.) Recall also the q-binomial coeff: k /===\ n - k + j n | | 1 - q [ ] := | | --------------, k | | j j = 1 1 - q which becomes the vanilla one when q -> 1. 2 p n What is known about the remainder mod 1-q^p ? E.g., for [ ] p n it's 2 n p 2 n ( ) - ( ) p n p n 1 - q 2 n --------------- ------ + ( ), p 1 - q n which gives the sizes of the residue classes when p n distinct positive integers <= 2 p n are summed mod p. E.g., the probability that the sum of 1000 distinct integers from [1,2000] will be divisible by 5 is 2 n ( ) 1 n 1 (1 - -) --------- + - p 2 n p p ( ) n p with p = 5 and n = 200, roughly 1/5 + 4.021284314257178521246*10^-482. The other four residues are equally probable, very roughly 1/5 - 10^-482.

From 75240.125@compuserve.com Wed May 31 05:44:10 1995 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 31 May 1995 02:45:25 MST Received: from dub-img-2.compuserve.com by optima.cs.arizona.edu (5.65c/15) via SMTP id AA27641; Wed, 31 May 1995 02:45:21 MST Received: by dub-img-2.compuserve.com (8.6.10/5.950515) id FAA11025; Wed, 31 May 1995 05:45:07 -0400 Date: 31 May 95 05:44:10 EDT From: "Fred W. Helenius" <75240.125@compuserve.com> To: math-fun <math-fun@cs.arizona.edu> Subject: Re: doubling mod P Message-Id: <950531094409_75240.125_HHB42-1@CompuServe.COM>

I think that the search for numbers like 1093 & 3511 has reached at least 1G, but don't know details.

I think I've heard these numbers named after Wieferich. Even more exclusive is 3*11*179, the only known pseudoprime satisfying

binom(p-1,(p-1)/2) == (-1)^((p-1)/2) mod p.

I've found two other members of this exclusive club. They turn out to be the squares of the two Wieferich primes: 1093^2 = 1194649 and 3511^2 = 12327121. An outline proof: (1) If q is a Wieferich prime, then binom(q-1,(q-1)/2) == (-1)^((q-1)/2) mod q^2. This is an immediate consequence of Hardy & Wright's Theorem 133. (2) If q is an odd prime, then binom(q^2-1,(q^2-1)/2) == (-1)^((q-1)/2) binom(q-1,(q-1)/2) mod q^2. This follows from writing the first binomial as the product of terms (q^2 - k)/k, 1 <= k <= (q^2-1)/2. For q(q-1)/2 of the terms, the numerator and denominator are free of q, so each of these terms reduces to -1 mod q^2; the remaining (q-1)/2 terms form the second binomial. Combining (1) and (2), for a Wieferich prime q, binom(q^2-1,(q^2-1)/2) == 1 mod q^2, which is the original condition with p replaced by q^2.

From rwg@NEWTON.Macsyma.COM Thu Jun 1 00:39:00 1995 Received: from optima.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Thu, 1 Jun 1995 01:06:08 MST Received: from newton.macsyma.com by optima.cs.arizona.edu (5.65c/15) via SMTP id AA17460; Thu, 1 Jun 1995 01:06:05 MST Received: from SWEATHOUSE.macsyma.com ([192.233.166.105]) by NEWTON.Macsyma.COM via INTERNET with SMTP id 321147; 1 Jun 1995 03:39:30-0400 Date: Thu, 1 Jun 1995 00:39-0700 From: Bill Gosper <rwg@NEWTON.macsyma.com> Subject: Re: doubling mod P To: 75240.125@compuserve.com Cc: math-fun@cs.arizona.edu In-Reply-To: <950531094409_75240.125_HHB42-1@CompuServe.COM> Message-Id: <19950601073915.9.RWG@SWEATHOUSE.macsyma.com>

> I think I've heard these numbers named after Wieferich. Even more > exclusive is 3*11*179, the only known pseudoprime satisfying > > binom(p-1,(p-1)/2) == (-1)^((p-1)/2) mod p. I've found two other members of this exclusive club. They turn out to be the squares of the two Wieferich primes: 1093^2 = 1194649 and 3511^2 = 12327121. Gack, retroactive deja vu. I think this may have been in Ilan Vardi's Mathematica book.