From: [Permission pending]
Subject: Re: number theory [k*2^n+1]
To: rusin@math.niu.edu (Dave Rusin)
Date: Sat, 9 Dec 1995 16:45:49 +0000 (GMT)

Dave,

You write:
> 
> In article <[identifier deleted]> you write:
> >It is a mildly notorious open problem to prove that there is some prime
> >k*2^n + 1 for every odd k < 78557. There were 118 such k's for which no prime 
> >was known in the first edition of [UPINT] (1981), and this was down to 35
> >by the second edition (1994).
> 
> What about those of us with often-idle workstations which can quickly check
> primality; do any of those 35 remaining   k's  have small enough  n's  still
> unchecked that a month or two of CPU time is likely to be helpful? 

UPINT (2nd edition) says that the remaining 35 have all been checked up to 
n=50000, so we probably need arithmetic FFT implementations to continue the 
searches efficiently.

It is of some interest to guestimate how far one might have to go. Many of the
remaining k's have "almost covering" congruences, as one might expect. For 
example, all 35 of them have all but one value of n mod 4 knocked out by 3.5, 
and 20 of the 35 (I'm a bit suprised it isn't more) have all but one residue 
mod 12 knocked out by 3.5.7.13. Of course, this means one has fewer n's to do 
Fermat tests for, up to a given limit, but it is correspndingly less likely one 
will find a prime.

Ignoring that aspect and assuming that the n's that make k*2^n + 1 prime will have
statistics something like the indices of Mersenne primes, with a density ~ K log x,
K = 2+abit, then going up to n=500000 would have a fair chance of eliminating the
last of the remaining 35. In this context, one should recall that there are gaps 
above 200000 in the documented coverage of Mersenne prime indices.

The text and references in UPINT suggest that the person most likely to know the
up-to-the-minute status of any searches going on is Wilfrid Keller.

[sig deleted -- djr]

==============================================================================

From: [Permission pending]
Subject: Re: number theory [k*2^n+1] (2)
To: rusin@math.niu.edu
Date: Sat, 9 Dec 1995 17:02:05 +0000 (GMT)

Dave,

Looking at that again, I think that the comparison with Mersenne primes may 
be seriously over-optimisitic! The eliminating congruences in the Mersenne
case are "maximally overlapping", in that they are just eliminate 0 (mod 2),
0 (mod 3), 0 (mod 5), ... and one gets nothing from the non-primes. (Similarly
they are "almost covering" in the Fermat case, eliminating everything except 
the powers of two.) I suspect that the true search limit needed may be more 
like 5000000 than 500000.

[sig deleted -- djr]