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]