The Sierpinski Problem

A Sierpinski number is an odd number k such that no number of the form k.2n + 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, k0. Below 78557, there are 178 odd values of k for which no number of the form k.2n + 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 < 105, 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.2n + 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.

 82841 1036 1037, 1247, 1479, 1601, 7763, 9917 (19154) 99769 256 1042, 1834, 8938, 11818 (26177) 88157 641 1063, 1579, 18863 (20670) 84887 851 1087, 1947, 5391, 6331, 6451, 6763, 11515 (18510) 95791 684 1088, 1404, 1548, 9272, 11888 (18215) 79879 457 1098 (22017) 97789 190 1102 (32313) 92749 643 1138, 1190, 12134 (18037) 80419 497 1166, 1946, 5366, 14966 (21757) 89537 477 1203, 18579 (25310) 93443 599 1277, 3633, 4945, 5377, 6485, 8473, 12893, 13673 (23196) 89003 137 1285, 4621, 12661 (33564) 81857 227 1399 (27462) 90047 311 1403 (24178) 81871 202 1420, 2164, 2956, 19132 (31299) 96409 223 1426 (27141) 82907 408 1475 (21514) 89521 420 1564, 9756 (21299) 79819 350 1678, 3598, 4510, 18742 (23309) 98723 822 1681, 1977, 2245, 4725 (20920) 91399 448 1746 (21473) 97621 216 1820, 6092 (27811) 98461 403 1892, 13088 (24163)

Surviving n £ 2000 : 45

 87469 334 2110 (24197) 97697 420 2139, 6451, 10203, 18507 (20178) 90949 271 2254, 5710 (25857) 82283 442 2469, 6273, 7281, 8889 (25508) 90529 126 2518 (35853) 94639 418 2654, 17350 (20653) 88007 331 2843, 2915, 23643 (24026) 82267 759 2904, 18000 (21751) 98327 184 2911 (31446) 99557 653 2931, 4827, 6479, 10323 (19738)

Surviving n £ 3000 : 35

 91291 182 3432, 3672 (31959) 90019 349 3470, 4574, 5462, 30062 (31893) 93593 358 3597, 7485 (22004) 86761 352 3896, 4808 (25027)

Surviving n £ 4000 : 31

 88549 486 4882 (21297) 92119 448 4882, 11186 (20385)

Surviving n £ 5000 : 29

 92567 275 5063 (26710) 97555 618 5196, 8252, 21060 (21539) 81919 78 5602 (52545) 96983 555 5917, 10473 (18528)

Surviving n £ 6000 : 25

 81091 101 6504 (37703) 99587 189 6747, 9807 (35534)

Surviving n £ 7000 : 23

 82549 388 7530, 7974 (22713)

Surviving n £ 8000 : 22

none in this range

Surviving n £ 9000 : 22

 94069 221 9098 (26473) 93331 266 9656 (25583)

Surviving n £ 10000 : 20

 86869 217 11542 (26157) 85711 453 12696, 12804 (21635) 81269 591 12979, 15607, 17467 (18880) 80839 356 15030 (25901) 98431 369 15880, 18848 (22287) 93617 324 17587 (22986) 86701 214 17768 (25663)

Surviving n £ 30000 : 13

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

 89059 176 33834 (39569) 84409 259 38070 (38989)

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

 79309 56 (76933) 79817 146 (43678) 85013 209 (43664) 86747 311 (39302) 87743 266 (38804) 89225 601 (34378) 90527 207 (40198) 91549 140 (45053) 94373 140 (43516) 98749 332 (37849) 99739 190 (43577)

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

 n range 1k 2k 3k 4k 5k 6k 7k 8k 9k 10-20k 20-30k 30+k count 34 14 7 9 9 10 5 4 6 31 2 3