My goal was "inverting" Pratt succinct certificates of primeness, by constructing new primes from primes that already have Pratt certificates. Primes of the form 1+2*p^k, where p already has a certificate, can be given a certificate which is an extension of the certificate of p. These primes aren't just "primes with high probability", but actual provable primes. The problem is that finding such extensions gets harder & harder. For example, primes of the form 1+2*17^i are quite rare (i=47 works). Primes of the form 1+2*47^i are also quite rate (i=175 works). This means that trying to force an extension for a particular Pratt prime is going to be quite wasteful; better to keep the search very wide. At 06:49 AM 10/25/2015, James Propp wrote:

1+2*5^0=3 is prime, 1+2*5^3=251 is prime, 1+2*5^251 is prime, ... ? ...

(Maybe this progression was implicit in Henry's post, but I thought it deserved explicit mention.)

Jim Propp

On Sunday, October 25, 2015, Henry Baker <hbaker1@pipeline.com> wrote:

...

1+2*251^251 is prime. Lisp's integer-length returns 2002 bits.

251 = 1+2*5^3 and is prime.

Kinda cool!