Sierpinski's Problem to One Million

Joseph McLean

Sierpinski's Problem is to remove as many odd k from consideration as Sierpinski numbers by finding primes of the form k.2n +1, if necessary by pushing n to very high limits, and as a by-product, locating some very large primes in the process. For convenience, I make the following definitions :

A Keller prime is a prime of the form k.2n +1, where k is odd, and for which none of the numbers k.2m +1 for 0 < m < n is prime.

The Keller prime for k, k being odd, is the smallest prime of the form k.2n +1, with n > 0.

I have previously considered all odd k between 78558 and 105. Of these, only 7 values of k still do not have a known Keller prime.

As a wholesale extension, I will now consider all odd k between 1 and 106. Again, I only consider values of k for which there is no prime of the form k.2n +1 for n £ 1000. A detailed breakdown of Keller prime counts for n £ 1000 is available on request. The counts of surviving k values, broken down into ranges of x.105 to (x+1).105 are as follows :

 x k 0 247 1 269 2 271 3 298 4 298 5 310 6 302 7 318 8 303 9 315 Total 2931

The Nash weight of each of these was calculated to give some idea of the relative difficulty of searching. Additionally, given the nature of the values involved, this is a convenient method of obtaining values with Nash weight less than 100. These are useful when searching for very large primes. Nash weights are split as follows :

 x w = 0 <100 <200 <300 <400 <500 <600 <700 <800 <900 <1000 others totals 0 1 11 40 58 49 41 21 11 7 6 1 1 247 1 0 6 40 76 51 44 27 13 7 3 2 0 269 2 2 10 52 65 55 38 23 8 10 4 2 2 271 3 2 10 49 85 64 35 27 12 8 1 2 3 298 4 1 6 46 78 70 45 27 14 7 2 2 0 298 5 1 10 46 81 61 54 25 20 5 4 2 1 310 6 1 7 48 59 73 51 28 18 9 4 3 1 302 7 0 7 46 78 69 50 29 19 9 3 3 5 318 8 0 6 48 65 74 46 28 16 10 5 4 1 303 9 3 5 51 75 63 47 27 21 12 5 3 3 315 tot 11 78 466 720 629 451 262 152 84 37 24 17 2931

A Nash weight of zero indicates a Sierpinski number. These, with covering sets, are :

78557  - {3, 5, 7, 13, 19, 37, 73}

271129 - {3, 5, 7, 13, 17, 241}

271577 - {3, 5, 7, 13, 17, 241}

322523 - {3, 5, 7, 13, 37, 73, 109}

327739 - {3, 5, 7, 13, 17, 97, 257}

482719 - {3, 5, 7, 13, 17, 241}

575041 - {3, 5, 7, 13, 17, 241}

603713 - {3, 5, 7, 13, 17, 241}

903983 - {3, 5, 7, 13, 17, 241}

934909 - {3, 5, 7, 13, 19, 73, 109}

965431 - {3, 5, 7, 13, 17, 241}

For each of the k with a Nash weight greater than zero, the search limit was initially pushed up to 4000. This removes more than half of the values, leaving, for each subrange :

 x k 0 128 1 134 2 149 3 146 4 133 5 151 6 142 7 138 8 148 9 144 Total 1413

These counts include Sierpinski numbers.

For each of these k, the search limit was then pushed up to 10000, leaving, by subrange :

 x k 0 88 1 85 2 102 3 96 4 90 5 95 6 94 7 85 8 100 9 93 Total 928

The remaining k are then treated individually with no common search limit. If a Keller prime is found, the search will generally be halted immediately, unless the Nash weight is low. In this case, the search for large Robinson primes takes over, as explained elsewhere. The following is a list of all k that have no Keller prime up to n = 10000, together with their Keller primes if known. Sierpinski numbers are marked with asterisks. An up-to-date list of factors is available in text form.

 3061   33288 32161   43796 54767   1337287 78181   22024 4847   3321063 33661   7031232 55459 78557   ***** 5297   50011 34711   10464 59569   390454 79309 5359   5054502 34999   462058 60443   95901 79817 5897   22619 36983   38573 60541   176340 80839   15030 7013   126113 37561   16604 62093   18353 81269   12979 7651   25368 39079   26506 62761   15064 84409   38070 8423   55157 39781   176088 63017   53195 85013   699333 10223   31172165 40547   12983 64007   26015 85711   12696 13787   53135 44131   995972 65567   1013803 86701   17768 14027   40639 44903   17913 67193   16249 86747   42051 16817   42155 46157   698207 67607 86869   11542 18107   21279 46187   104907 67759   10402 87743   212565 19249   13018586 46471   96640 69107   16599 89059   33834 20851   10672 47897   61871 69109   1157446 89225   92067 21181 48833   167897 71417   26807 90527   9162167 22699 49219   16102 71671   28884 91549 24737 50693   32753 74191   20340 93617   17587 25819   111842 51917   18031 74269   167546 94373   3206717 27653   9167433 53941   36944 75841   31220 98431   15880 27923   158625 54001   16652 76759   17446 98749   1045226 28433   7830457 54739   14282 77899   43194 99739

 101869   77002 132439   23158 156889   65082 181639   27042 101911   10560 134131   19248 159503   540945 181921   148432 102259   19070 135887   32319 161041   7107964 182749   14890 102263   52853 137269   21958 161509   17154 183091   43984 105857   49155 137401   40956 161957   727995 183347   116399 106853   50061 138199   74670 163187 184609   23130 107929   1007898 139201   14752 163463   10069 185449   435402 110941   12340 142099   70802 165499   79638 185993   164613 112097   17539 145609   23798 167551   26092 187681   573816 114751   11064 146761   56816 167957   417463 190999   54478 115561   91548 147143   16973 168451 191537   34067 117557   51511 147391   120616 168587   545971 193801   26344 118069   27078 147559   2562218 169639   31018 193997 118081   145836 149183   1666957 170399   17995 196307   50267 118249   80422 151945   62876 172127   448743 197753   73745 122149   578806 152183   20333 172157   71995 198113   267005 123287   2538167 152267 173633   16177 198647   178863 128239   88330 153169   30478 173933   340181 198677   2950515 128449   109130 153263   21309 177421   69880 199037   101723 128789   31049 154801   1305084 177803   28653 130337   11563 155357   79679 179581   117980 131179 156511 179791   331740

 200749 225679   620678 260251   14556 282049   21634 201407   20247 225931 261203   354561 283741   32592 202705 227723 261917   704227 284843   13517 203749   13014 227753   91397 263329   406934 285473 203761   384628 229673 263927   639599 285601 203941   23004 231797   66503 264451   11940 286037 206821   22868 235351   13048 264977   26395 286051   13856 208381   463068 235607   60635 265711   4858008 286579   33842 209611 237019 267893   12237 287003   23169 210917   16251 237413   267149 268021   27844 287393 211195   3224974 238411 269041   10668 287509   17362 212671   15816 239063   21761 269153   12377 287899   223886 214519   1929114 240211   93184 270557   111807 288151   73752 214583   25225 240713   11497 271129   ***** 289171 216751   903792 241489   1365062 271577   ***** 289939   48286 218447   12667 244609   12050 272341 290281   61872 219259   1300450 246053   44673 273631   30340 291979   65182 220639   29650 247099   484190 273679 293723   16517 222113 250163   198453 274699 294181 222169   18338 250463   1316921 277217   72227 294241   184040 222361   2854840 252181   149684 278209   25518 297257   28211 222379   12842 255811   140148 278837   10031 297317   54755 223127   50959 256787   11455 278843   51801 297617   60187 224027   273967 258317   5450519 279361 299239   98714 224657   36391 258541   25308 279767 225077   20047 259733   29973 281543   440853

 300649   23846 328703   17949 356599   15234 376879   13946 300661   22084 329221   19508 356809   35922 381811   17124 302701   71716 331883   119945 356971   156572 381991   14224 303001   12868 332093   18349 357017   332367 382247 303197   29047 334519   10902 357271 382849   15598 305063 335299   78574 359551   111552 383717   325171 305147 335453   28633 359747   11235 383843   87973 305363   22385 335957   30331 359933 385313   142989 305807   12511 336143   49353 360331 385789   15658 306893   117721 336923   12649 362281   11172 388561   16956 307877   27435 337111   229176 362881 389401   171604 308237   48491 337651   31492 363917 389581   75348 308423   395337 340171   31976 364969   98546 390533   13761 310339 340441 365033   23121 391681   52736 311267   89215 340471   128256 365221 392033 311573 340759 365867 393091   16204 312121 348169   17166 366467   88163 393497   255283 312469   64970 348353   19585 366953 394429   16626 312863   293881 348587   99519 368299 396203 315409   12294 350689   250850 369497   183079 397309   296070 322523   ***** 351167 371027   103775 398089   11794 324169   15802 352217   26827 374093   36925 398597   34779 327679   24046 353239   12906 376141   87980 399481   48792 327739   ***** 354203   95549 376463   13197 399617   340955

 400613 427339   78174 450589   67886 475817   14767 401131   37932 427517   82787 451051   29360 479783 401371   62400 428387   21123 451351 480863   25785 402407   34875 428657 451975   11650 481727 404177   10511 430303   87694 452003   48185 482719   ***** 408379   27854 430727   88875 452119 483233   48389 409279   27662 432257   12203 452131   18836 483661   14088 411953   78929 432983   259453 452371   190272 484763 412081   145336 433261   11652 454159   24158 487681   19180 412367   25779 433457 456211   325780 487819   27486 412591 437933   51817 456347   50039 488341 413537   92055 438541   60832 457217 488581   27344 413873   32701 438773   11357 459893   11377 488641   13804 415313   26481 440837   24831 462829 488843   18493 415427   50571 441923 464929   59426 489977   49299 415523   11393 443701   30008 465407   159915 491147 418487   10771 445373   16377 467543   21185 492953   260957 418591 446509   557118 467963   132769 495979 419093   42161 446633   107905 469073   104969 498107   22483 420113 447061 470477   17471 498781 422491 447079   50514 470693   35533 499561 423083   23817 447271   10856 473567 425149   80674 450139   54914 475549   12194

 501107 529759   10922 554659   18470 574907   14395 501143   113609 532703 556667   86543 575041   ***** 502613 533213   11045 556697   13371 575539   431950 504199   37794 536329   27362 557693   117549 575791   10760 506749 536779   67590 559051   33872 578689   66070 507743   30133 536839 559549   25158 583189 508217   16343 538313   66301 561769 583441   14328 509101   14952 538943 562487   18603 583561   10724 510893 540977   188027 564511   82868 583939   12290 515161   17832 541877   82575 565681   14104 587417   10983 515357 541939   16522 566011   16464 588317 515611   15256 542093   11177 566569 589021 517651   204528 544433   16805 567587   18935 590033 517883   14533 545401 568067   107603 591323   13477 517913 545959   30014 569581   11572 593417   43043 518671 546529   264498 570601   65040 593689   12030 522001   39244 548033 570923   207189 594151   22264 523547   25203 548869   304442 571969   10262 596959   22294 523669   202714 550429   12894 572029   52890 597211   26912 524663   423169 551071   25260 572213   66409 597323   21949 525409   98942 552203   57841 572491   37860 599003 527791   51192 552593   24517 572507   133971 599011 528139   12050 553159 573271   42820 599513 529157   22171 554573   305373 574061   13317

 602537   19939 621953   151469 652291   27960 678739   16638 603593   12221 624139   53814 653063 680597   10399 603713   ***** 624511   962636 653693   93457 680851 603767 626303 654083   217533 682141   36628 604189   500578 626419   211622 655367   16171 682667   15955 606199 629089   11966 656123 683087   18563 607801   190960 629149   52250 656753 684977   14543 608179   32854 630121 659237   11295 686479   372062 609227 632663 662345   10099 687347   12087 609769 633197   73171 662899   42658 688819   36538 610097   330651 633407   16627 663827   65447 689281   17724 612263   112221 633481 665101   10116 692063   20293 612773   51941 633841   26868 665423 692431   56560 614617   21150 634441   14928 667861 693769   247742 615151   800316 637501   20440 670309 694879   169326 616367   30915 639827   32291 670969   36346 694891   33428 618379   143758 644333   23401 672481   10896 694973 618889   15574 646411   23372 673009   60186 695659   10378 618893   11845 646427   67667 673667   11963 695911   28156 619013   849281 646757   20963 674477 696323   15057 619399   150478 646937   23223 675559   23858 696661   134472 619403   76141 648751 678047   74863 697831   12476 620063   15825 651661   17268 678109   54994 621437   16455 652067   12155 678173

 700141   11572 724351 754939   10062 777559 700339   21630 725483   37421 756139   28594 778021   55132 700637   14795 730831   13272 757343 783019   235798 701123   57057 731041   21884 758243   161705 784159   11310 701357 733193   22265 759653   154085 785209   37266 702707 734147 760283   13729 787489   19634 703643 734753   77481 760583 787981   36844 706627   18322 735287   10883 761749 791273   14557 708263   20673 736249 762227   325531 791491   17468 709187   30675 736999   10026 762769   188586 791867   13387 710603   12513 741301   14780 766531 793051   14984 711721   13116 743357 766801 793561   19576 711833 745337   27295 769343 793817   106719 714563 745673   45969 769861   41364 794867 715531   178144 747379   49742 770867   14975 795983 717001   58936 749447 770899   25346 796493   17745 718463   199345 749971 771977   21339 797131   39472 718849 750083 772403   13277 797903   26677 719611   79296 751103   26481 772969   26754 799951   13500 720121   86960 751613   31745 774977   261235 721141 751999 775969   181806 721969   250898 753047   16115 777503   22493

 801349   27426 822083   670761 846857   453343 877583   17521 801923   690713 822631   11424 850337   11307 877997   21395 802367   47495 823969 851537   18295 878029 802493   24341 826201 852019 879049 802613 829013   457421 853817   23795 879497 804019   25462 829643 855017   12863 879919   23650 804173   22961 829681   13840 855949   16878 881537 804541   50676 831571   10492 856043 884723 804691   64628 833179   387618 856369   15350 885077   15891 804863   18045 835667   18907 856607   185727 885233   13625 805321   40024 835733   64485 858079 886699   14346 807203   11769 836161   69692 858527   14187 887153 808981   34548 836209   225602 859523   14629 888001   33892 810949   98090 838081   51712 861083   40441 889187   52975 811247   15635 838157   12847 861437   22007 889727   391475 812717   29091 838441   19248 863431   98416 890333   18561 812881   663152 840811   205948 865549   42098 892247   219359 813707   10567 841757   56951 867271 892249 815491   128160 842393   44681 867443   57845 894353   26713 816353   20041 843079 868531   27712 894409 817021   22584 843317   38771 870061 894827 817403   43897 843811   39228 872119 895579 818551   112120 844703   15445 873227   10243 895823   495837 819437 846347 875447   10027 896851   31308 821071   12656 846737   25751 876529   43242 899449

 900317   29263 928997   145355 957977 974483   69065 901067 930079   61386 958201   18868 976523   64801 903211   26344 931517   65647 959689   17778 977521   101792 903983   ***** 933511   36760 959929   141906 979039 904081   11616 934909   ***** 959971   44128 981623   33353 904489 936083   16009 960139   27378 982531   41652 907021   33968 937639   45566 960301   430616 982547   73643 908183   10809 939259   10298 961099 983027 909473   13569 941207   19535 961313   155421 983663   44377 910733   200233 941741   51345 961621   35996 984185   10165 911123   479981 941993   31745 963227   196403 988741   23532 911791   129892 942227   215687 963661   35212 989147 912721   47292 942233   32421 964549   82462 989567   31683 912889   10342 943373   304161 964673 990421   80560 913847   11127 943981   20672 965431   ***** 990721   22188 918001   11616 944011   372216 965689   23782 991037   10423 919291   14756 945499   42134 968491 991951   40688 922081   65840 947963   10225 969533   75885 992731   731740 922463   141321 951233   14673 969769   33270 993767   186619 923177 951593   159929 970457   11679 996811   16788 924683 951961   39888 971071   19716 997699   18902 924773   13121 953597   62719 971389 925907 954211   28976 972443   17033 927181   39656 956749   95966 972739

Keller primes in the above tables are credited to the following (in no particular order):

# Wildrid Keller

Jeff Young

Duncan Buell & Jeff Young

Joe McLean*

Jim Fougeron*

Jim McElhatton*

Dirk Augustin*

Dan Morenus*

Ray Ballinger @

Sander Hoogendoorn*

Kimmo Herranen*

Brian Schroeder*

Contributors from the Prime Sierpinski Project, administrated by Harsh Aggarwal

Nestor Melo @

Daval Davis @

Phil Carmody @

Pavlos Saridis @

Contributors from the Seventeen or Bust Project, administrated by Louis Helm, David Norris & Michael Garrison

Contributors from the Proth Prime Search project using Primegrid

The projects listed above cover particular subsets of the entire range under consideration. For any significant dent in the remainder, I have to thank contributors to my own co-ordinated search, who are marked with an asterisk. An ampersand indicates people whose help was invaluable in the earlier days of the search.

The complete searches to n = 100000, 200000 & 300000 is as follows:

 x k k k 0 37 29 28 1 33 24 23 2 48 43 40 3 40 31 26 4 33 27 25 5 36 31 27 6 36 29 26 7 35 28 25 8 38 35 32 9 33 24 22 Total 369 301 274

The above tables can be summarised as follows, where the counts are of k for which no Keller prime is known, including and excluding Sierpinski numbers.

 x k k exc 0 10 9 1 6 6 2 22 20 3 22 20 4 23 22 5 23 22 6 20 19 7 24 24 8 24 24 9 17 14 Total 191 180

The extended Sierpinski search to find Keller primes for the remaining values of k > 78557 not covered by any other project has an on-line status report updated regularly.

The number of outstanding k values left at each significant stage is as follows :

 search limit (on n) outstanding k values 1000 2931 2000 2002 3000 1645 4000 1413 5000 1282 10000 928 20000 701 50000 490 100000 369 200000 301 300000 274 500000 256 1000000 243

The figures up to 300000 have now been confirmed complete. Above this limit, the values are not exhaustive and so may drop.