The Sierpinski Problem

A Sierpinski number is an odd number k such that no number of the form k.2ⁿ + 1 is prime for any n > 0. The smallest Sierpinski number known is 78557, and it is suspected that this is actually the smallest Sierpinski number, k₀. Below 78557, there are 178 odd values of k for which no number of the form k.2ⁿ + 1 is prime for n £ 1000. Most investigations have concentrated on this range in order to remove as many k as possible from consideration. This has resulted in primes being found, sometimes for very large n, for all but 21 of the 178 in this range. In this article I shall report on investigations in the range 78557 < k < 10⁵, k odd, which provides another 68 values of k for which there is no prime with n £ 1000.

The standard method of attack is used, that is, to remove as many cases as possible using trial division and then apply Proth’s Test to those remaining. In the current search, this will be done using the Yves Gallot Proth program for Windows 95. The main aim is to find, for each k, the smallest n for which k.2ⁿ + 1 is prime, presuming that one exists.

It is often the case, depending on the divisibility properties for particular values of k, that after trial division there are very few cases left to test. It is then appropriate to push up the search limit in the hope of finding other very large primes. As well as being interesting in their own right, there is always the possibility that one of these primes may prove to be a factor of a Generalised Fermat number of the form for some small value of a, in particular a = 2, 3, 5, 6, 7, 10, 11 or 12. In order to decide how far to push the search limit for each k, I have elected to use a sieve designed by Chris Nash and implemented by Nash and Paul Jobling. This provides a list of simple congruences that are used to remove exponents from consideration. The standard Nash weight is then the number of exponents that survive the sieve for the 10000 exponents between 100001 and 110000.

Of the 68 values of k surviving n £ 1000, the limit on n was increased by Nash weight at least as follows :

< 200 : 30000

< 300 : 25000

< 400 : 22000

< 500 : 20000

others : 18000

before, if at least one prime was found, the search was halted. The following list gives, for each k, the Nash weight and the values of n that provide primes. The list is ordered on the smallest n. The numbers in brackets are the current search limits on n.

Surviving n £ 2000 : 45

Surviving n £ 3000 : 35

Surviving n £ 4000 : 31

Surviving n £ 5000 : 29

Surviving n £ 6000 : 25

Surviving n £ 7000 : 23

Surviving n £ 8000 : 22

none in this range

Surviving n £ 9000 : 22

Surviving n £ 10000 : 20

Surviving n £ 30000 : 13

For these 13 values of k, the search limits were be pushed much higher, producing the following large primes :

The remaining 11, together with their Nash weights and current search limits, are :

In the above, there are 134 primes listed. These fall into ranges as follows :

URL : www.glasgowg43.freeserve.co.uk/sierpin2.htm