Keller Primes - The Search Extended

The most convenient way of searching for large prime numbers is to consider the form p = k*2n +1 where k is odd and n ³ 1. Every odd prime can be represented in this form, usually with low values of n and high values of k. When k is small, there are well-known primality tests for p available, based on the factorisation of p- 1, in this case readily obtainable, and for which many practical computer implementations exist.

For most values of k, there will be at least one small value of n (n < 30 say) for which k*2n +1 is prime, but this is not always the case. For convenience, let us say that k is an m-survivor if and only if there are no primes of the form k*2n +1 for any n £ m. Furthermore, k*2m +1 is a known as a Keller prime if k is an (m- 1)-survivor but not an m-survivor, that is, a Keller prime is the smallest prime of the form k*2m +1 for a fixed value of k. Alternatively, a Keller prime is the first occurrence of a prime in the sequence {k*2n +1, n = 1, 2, …}. As m increases, the frequency of m-survivors decreases as more and more Keller primes are found.

The divisibility properties of k with respect to the sequence {k*2n +1} have a profound bearing on the number of potential values that survive initial sieves by small primes. Elsewhere, it is proved that if r exists such that a prime p divides k*2r +1, then p divides k*2n +1 if and only if n º r (mod e) where e is the order of p to the base 2. Moreover, this r is unique (mod e). The pairs (p, r) are called Nash congruences. Primes of order e consist of all prime divisors of 2e - 1 which do not divides 2f - 1 where f < e. The set of all Nash congruences up to a specific maximum exponent e is known as a Nash sieve. Note that throughout, k is a fixed value.

Without trial division, we have created a densest possible sieve (subject to one or two conditions). If we apply the Nash sieve over a fixed range of exponents then the count of exponents not covered is called the Nash weight, which is a measure of the susceptibility of k to trial sieving.

From the basic theory, it can be demonstrated that there exist k such that every value in the sequence {k*2n +1} is divisible by at least one of a covering set of primes, that is, no Keller prime exists. These values of k are known as Sierpinski numbers. Sierpinski numbers are m-survivors for all m.

The smallest known Sierpinski number is k0 = 78557, and this in fact is believed to be the smallest. However, there are currently 11 values of k < 78557 for which no Keller prime is known. There are two major coordinated searches underway at present to locate Keller primes for these, pushing search ranges to very high values of n.

I have previously considered the range 78557 < k < 105 and extended this upper limit to 106. In this article I will outline the further extension to 107.

The basic approach is to maintain a list of k values which are n-survivors, while pushing the value of n continually higher. The list initially consists of every odd value of k in the range. For low values of n, I use straightforward trial division to establish whether k*2n +1 is prime or not. Those values that provide primes are discarded and all others preserved. When trial division becomes unreasonable except as an initial sieve, for n > 10 say, I move on to the (p- 1)-primality test. At this point, the primeform software pfgw is the most convenient tool. Eventually, with the length of the survivor list becoming substantially smaller, and the exponents reasonably large, say over 300, it is more convenient to cover ranges of exponents at a time. For n up to 2000, it is most convenient to use my own routines using Ultrabasic, where I can use a built-in break if a Keller prime is found. Beyond this point, the optimised code of primeform and proth are preferred, even though there is a small percentage of unnecessary overhead involved without the automatic halt once a prime is found.

Covering larger ranges at a time, the process becomes 4-fold. First, I use my own routines to generate a lightly pre-sieved list of possible primes. Then I use proth as a more substantial sieve, using a manual sieve limit higher than the automatic limit. The survivors are passed to pfgw, first using the probable prime test only. Numbers that pass this stage are then subjected to a full primality test, again using pfgw. The list of primes so obtained is used to shorten the survivor list.

In addition to extending the range of the search, I have turned to the negative case and given it an identical and parallel treatment. Simply put, this means considering the form k*2n - 1, which has equivalent negative versions of Nash congruences and Keller numbers. Negative Sierpinski numbers are known as Riesel numbers. The process of creating and maintaining the survivor list is very similar to the positive case, the only difference being the removal of my own routines from use except to perform the stage one sieve, since the (p+1)-primality test is complicated and already provided efficiently within pfgw.

For n £ 1000, complete set of statistics of the numbers of survivors at each exponent value for both the positive and negative cases are available as spreadsheets. For n in excess of 1000, the numbers of Keller primes found at each exponent is very low, and it is more useful and meaningful to preserve a list of the primes.

Survivor counts at various exponent values are provided in the following table. Bear in mind that at the start, the complete list contains 5*106 values.

exponent

positive survivors

percentage

negative survivors

percentage

percentage

difference

1

4364564

87.29

4364830

87.30

- 0.00532

2

3807542

76.15

3807522

76.15

+0.00040

3

3363072

67.26

3363091

67.26

- 0.00038

4

2971601

59.43

2972702

59.45

- 0.02202

5

2675445

53.51

2676765

53.54

- 0.02640

6

2404196

48.08

2405279

48.11

- 0.02166

7

2189243

43.78

2189837

43.80

- 0.01188

8

1987415

39.75

1987029

39.74

+0.00772

9

1832786

36.66

1832589

36.65

+0.00394

10

1687099

33.74

1687067

33.74

+0.00064

20

918630

18.37

919838

18.40

- 0.02416

30

621053

12.42

621531

12.43

- 0.00956

40

466294

9.326

465966

9.319

+0.00656

50

375294

7.506

375036

7.501

+0.00516

60

312920

6.258

312610

6.252

+0.00620

70

270730

5.415

270997

5.420

- 0.00534

80

238883

4.778

239001

4.780

- 0.00236

90

214719

4.294

214602

4.292

+0.00234

100

194954

3.899

194829

3.897

+0.00250

200

106799

2.136

107112

2.142

- 0.00626

300

77410

1.548

77576

1.552

- 0.00332

400

62607

1.252

62649

1.253

- 0.00084

500

53330

1.067

53283

1.066

+0.00094

600

47038

0.9408

46981

0.9396

+0.00114

700

42543

0.8509

42389

0.8478

+0.00308

800

38949

0.7790

38904

0.7781

+0.00090

900

36097

0.7219

36108

0.7222

- 0.00022

1000

33813

0.67626

33803

0.67606

+0.00020

2000

22470

0.44940

22374

0.44748

+0.00192

3000

18076

0.36152

17971

0.35942

+0.00210

4000

15541

0.31082

15447

0.30894

+0.00188

5000

13909

0.27818

13800

0.27600

+0.00218

6000

12691

0.25382

12581

0.25162

+0.00220

7000

11749

0.23498

11700

0.23400

+0.00098

8000

11044

0.22088

10970

0.21940

+0.00148

9000

10479

0.20958

10359

0.20718

+0.00240

10000

10017

0.20034

9882

0.19764

+0.00270

Note that the positive survivor count includes 69 values of k identified as Sierpinski numbers, and the negative survivor count includes 65 values identified as Riesel numbers. One can see the very close correlation between the positive and negative counts, reflecting the duality of divisibility patterns.

Values of k which have high Nash weight will tend to require more testing than those with low Nash weight, since more exponents survive trial division. On the other hand, it is more likely that they will produce primes earlier in the search. The standard Nash weight is calculated over the k range 100001 to 110000, with an exponent limit of 256, and a Nash weight in excess of 1000 is considered to be particularly high. We would therefore expect the number of such k remaining in the survivor list to drop at a faster rate than the list length itself. The following table shows this explicitly, for the positive case only.

search limit

count of surviving high Nash weights

1000

362

2000

108

3000

57

4000

33

5000

20

6000

15

7000

13

8000

11

9000

9

10000

8

The percentage drop for all survivors between n = 1000 and n = 10000 is approximately 70%, whereas the equivalent drop for those of Nash weight ³ 1000 is almost 98%.

In the positive case, the first exponent value that does not provide any Keller primes is n = 2059. Thereafter, the number of such exponents increases in frequency. This sequence continues 2106, 2215, 2234, 2256, 2401, 2563, 2641, 2652, 2659, 2692, 2693, 2788, 2822, 2880, 2908, 2948, 2983, 3061, 3097, 3100, etc. The first occurrence of two consecutive exponents providing no Keller primes is 2692 & 2693. Analogously, the first run of three consecutive exponents providing no Keller prime is {4090, 4091, 4092}, the first run of four begins at 4152, five at 5087, six and seven at 6548, eight to thirteen at 7699, and fourteen at 9115.

Equivalently, in the negative case, the first exponent not providing any Keller primes is n = 2267, with the sequence continuing 2301, 2513, 2613, 2680, 2691, 2737, 2773, 2823, etc. The first occurrence of a pair of consecutive exponents giving no Keller primes is 2933 & 2934, the first run of three begins at 3580, four at 4854, five at 6497, six to eight at 6978, and nine to twelve at 8107.

The first dual occurrence of an exponent giving no positive or negative Keller primes is n = 3279, the first dual pair is at n = 4082, the first run of three begins at 5640, and four and five at 7401.

In the previous version of the positive side of this search, when exponent n = 10000 was reached, the survivors were passed out to interested collaborators to proceed further. Allocation of survivors was basically random, and the contributors were (and still are!) allowed to pursue individual searches as they saw fit, as long as they informed me of any primes discovered, and search limits otherwise. However, faster computers and the available software allow me to continue on my own much further. The following table gives the survivor statistics up to n = 20000.

exponent

positive survivors

percentage

negative survivors

percentage

11000

9586

0.19172

9499

0.18998

12000

9226

0.18452

9135

0.18270

13000

8916

0.17832

8835

0.17670

14000

8634

0.17268

8545

0.17090

15000

8391

0.16782

8305

0.16610

16000

8150

0.16300

8064

0.16128

17000

7940

0.15880

7857

0.15714

18000

7738

0.15476

7669

0.15338

19000

7542

0.15084

7490

0.14980

20000

7400

0.14800

7301

0.14602

This process is continuing, so please contact me if you are interested in finding out the current search limits. Lists of 1000-survivors and Keller primes for both the positive and negative cases are also available.