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.