Robinson Primes and the Sierpinski Problem

 

All primes must of necessity be of the form k.2n +1 for some odd k and some value of n. However, in view of the requirement for factors of Fermat Numbers, it is of interest to locate particular instances where either k is small and n is pushed as far as possible, or where n is small and k is pushed as far as possible. Viewed in this way, they are known as Robinson primes.

The following is a list of all values of n 4000 for each odd k < 100 such that k.2n + 1 is a prime. The number of such n for each k is also given.

k

p

n

1

5

1, 2, 4, 8, 16 (Fermat Primes)

3

24

1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912

5

13

1, 3, 7, 13, 15, 25, 39, 55, 75, 85, 127, 1947, 3313

7

21

2, 4, 6, 14, 20, 26, 50, 52, 92, 120, 174, 180, 190, 290, 320, 390, 432, 616, 830, 1804, 2256

9

31

1, 2, 3, 6, 7, 11, 14, 17, 33, 42, 43, 63, 65, 67, 81, 134, 162, 206, 211, 366, 663, 782, 1305, 1411, 1494, 2297, 2826, 3230, 3354, 3417, 3690

11

13

1, 3, 5, 7, 19, 21, 43, 81, 125, 127, 209, 211, 3225

13

10

2, 8, 10, 20, 28, 82, 188, 308, 316, 1000

15

26

1, 2, 4, 9, 10, 12, 27, 37, 38, 44, 48, 78, 112, 168, 229, 297, 339, 517, 522, 654, 900, 1518, 2808, 2875, 3128, 3888

17

12

3, 15, 27, 51, 147, 243, 267, 347, 471, 747, 2163, 3087

19

6

6, 10, 46, 366, 1246, 2038

21

23

1, 4, 5, 7, 9, 12, 16, 17, 41, 124, 128, 129, 187, 209, 276, 313, 397, 899, 1532, 1613, 1969, 2245, 2733

23

14

1, 9, 13, 29, 41, 49, 69, 73, 341, 381, 389, 649, 1961, 3929

25

24

2, 4, 6, 10, 20, 22, 52, 64, 78, 184, 232, 268, 340, 448, 554, 664, 740, 748, 1280, 1328, 1640, 3314, 3904, 3938

27

26

2, 4, 7, 16, 19, 20, 22, 26, 40, 44, 46, 47, 50, 56, 59, 64, 92, 175, 215, 275, 407, 455, 1076, 1090, 3080, 3322

29

20

1, 3, 5, 11, 27, 43, 57, 75, 77, 93, 103, 143, 185, 231, 245, 391, 1053, 1175, 2027, 3627

31

8

8, 60, 68, 140, 216, 416, 1808, 1944

33

21

1, 6, 13, 18, 21, 22, 25, 28, 66, 93, 118, 289, 412, 453, 525, 726, 828, 1420, 1630, 3076, 3118

35

20

1, 3, 7, 9, 13, 15, 31, 45, 47, 49, 55, 147, 245, 327, 355, 663, 1423, 1443, 2493, 3627

37

26

2, 4, 8, 10, 12, 16, 22, 26, 68, 82, 84, 106, 110, 166, 236, 254, 286, 290, 712, 1240, 1706, 1804, 1904, 2240, 2632, 3104

39

30

1, 2, 3, 5, 7, 10, 11, 13, 14, 18, 21, 22, 31, 42, 67, 70, 71, 73, 251, 370, 375, 389, 407,518, 818, 865, 1057, 1602, 2211, 3049

41

7

1, 11, 19, 215, 289, 379, 1991

43

17

2, 6, 12, 18, 26, 32, 94, 98, 104, 144, 158, 252, 778, 1076, 2974, 3022, 3528

45

16

2, 9, 12, 14, 23, 24, 29, 60, 189, 200, 333, 372, 443, 464, 801, 1374

47

2

583, 1483

49

12

2, 6, 10, 30, 42, 54, 66, 118, 390, 594, 1202, 2334

51

28

1, 3, 7, 9, 13, 17, 25, 43, 53, 83, 89, 92, 119, 175, 187, 257, 263, 267, 321, 333, 695, 825, 1485, 1917, 2660, 2967, 3447, 3659

53

14

1, 5, 17, 21, 61, 85, 93, 105, 133, 485, 857, 1665, 2133, 2765

55

15

4, 8, 16, 22, 32, 94, 220, 244, 262, 286, 344, 356, 392, 1996, 2744

57

22

2, 3, 7, 8, 10, 16, 18, 19, 40, 48, 55, 90, 96, 98, 190, 398, 456, 502, 719, 1312, 1399, 1828

59

7

5, 11, 27, 35, 291, 1085, 2685

61

6

4, 12, 48, 88, 168, 3328

63

37

1, 4, 5, 9, 10, 14, 17, 18, 21, 25, 37, 38, 44, 60, 65, 94, 133, 153, 228, 280, 314, 326, 334, 340, 410, 429, 626, 693, 741, 768, 1150, 1290, 1441, 2424, 2478, 3024, 3293

65

29

1, 3, 5, 11, 17, 21, 29, 47, 85, 93, 129, 151, 205, 239, 257, 271, 307, 351, 397, 479, 553, 1317, 1631, 1737, 1859, 1917, 1999, 2353, 3477

67

26

2, 6, 14, 20, 44, 66, 74, 102, 134, 214, 236, 238, 342, 354, 382, 454, 470, 598, 726, 870, 1148, 1366, 1692, 1782, 1870, 3602

69

17

1, 2, 10, 14, 19, 26, 50, 55, 145, 515, 842, 1450, 2159, 2290, 2306, 2335, 3379

71

14

3, 5, 9, 19, 23, 27, 57, 59, 65, 119, 299, 417, 705, 2255

73

16

2, 6, 14, 24, 30, 32, 42, 44, 60, 110, 212, 230, 1892, 1974, 2210, 3596

75

30

1, 3, 4, 6, 7, 10, 12, 34, 43, 51, 57, 60, 63, 67, 87, 102, 163, 222, 247, 312, 397, 430, 675, 831, 984, 1018, 1054, 1615, 2017, 2157

77

11

3, 7, 19, 23, 95, 287, 483, 559, 655, 667, 1639

79

9

2, 10, 46, 206, 538, 970, 1330, 1766, 2162

81

44

1, 4, 5, 7, 12, 15, 16, 21, 25, 27, 32, 35, 36, 39, 48, 89, 104, 121, 125, 148, 152, 267, 271, 277, 296, 324, 344, 396, 421, 436, 447, 539, 577, 592, 711, 809, 852, 1384, 1972, 2624, 2829, 3497, 3945, 3995

83

9

1, 5, 157, 181, 233, 373, 2425, 2773, 3253

85

18

4, 6, 10, 30, 34, 36, 38, 74, 88, 94, 148, 200, 624, 1300, 2458, 2556, 3638, 3834

87

17

2, 6, 8, 18, 26, 56, 78, 86, 104, 134, 207, 518, 602, 1268, 1302, 2324, 2372

89

11

1, 7, 9, 21, 37, 61, 589, 711, 1537, 1921, 3217

91

4

8, 168, 260, 696

93

27

2, 4, 6, 10, 12, 30, 42, 44, 52, 70, 76, 108, 122, 164, 170, 226, 298, 398, 686, 1020, 1110, 1478, 1646, 2032, 2066, 2800, 2816

95

25

1, 3, 5, 7, 13, 17, 21, 53, 57, 61, 83, 89, 111, 167, 175, 237, 533, 621, 661, 753, 993, 1039, 1849, 1987, 3437

97

12

2, 4, 14, 20, 40, 266, 400, 652, 722, 2026, 2732, 3880

99

33

1, 2, 5, 6, 10, 11, 22, 31, 33, 34, 41, 42, 53, 58, 65, 82, 126, 143, 162, 170, 186, 189, 206, 211, 270, 319, 369, 410, 433, 631, 894, 1617, 2025

 

The following is a list of the 50 odd k < 1000 for which there is no prime for n 10, and giving the lowest such n.

k

n

k

n

k

n

k

n

k

n

47

583

259

38

383

6393

605

11

773

53

103

16

263

29

389

11

607

12

797

35

143

53

283

30

437

23

631

144

811

16

197

15

335

19

451

12

647

15

827

19

203

13

351

12

467

19

649

22

829

18

211

20

353

21

481

64

689

15

881

1027

217

66

361

28

533

13

733

12

901

12

227

11

367

12

569

15

751

12

913

18

241

36

377

11

587

227

767

23

917

27

257

279

379

14

601

16

769

14

991

16

Table 1.

The following is a list of 104 odd k < 10000 for which there is no prime for n 100, giving the lowest such n, if found, and the search limit if not.

k

n

 

k

n

 

k

n

 

k

n

47

583

 

3331

172

 

5459

133

 

8021

119

257

279

 

3409

106

 

5483

137

 

8119

1162

383

6393

 

3443

3137

 

5771

167

 

8245

658

587

227

 

3529

122

 

5881

156

 

8269

1150

631

144

 

3533

261

 

5897

(20170)

 

8423

(8000)

881

1027

 

3589

118

 

6319

4606

 

8479

322

1021

112

 

3721

444

 

6353

785

 

8543

5793

1201

960

 

3797

315

 

6379

1014

 

8573

165

1277

143

 

3827

207

 

6439

578

 

8749

278

1523

145

 

3829

1230

 

6677

319

 

8791

268

1643

1465

 

3983

389

 

6719

103

 

8911

244

1669

230

 

4189

114

 

6721

208

 

8929

1966

1699

426

 

4283

689

 

6767

279

 

8933

261

1727

367

 

4337

103

 

6889

326

 

8957

115

1741

304

 

4367

715

 

6911

263

 

8989

418

1951

132

 

4429

342

 

7013

(24160)

 

9049

262

2033

221

 

4727

227

 

7141

128

 

9053

241

2057

295

 

4801

752

 

7201

964

 

9091

204

2303

189

 

4847

(12062)

 

7397

135

 

9181

136

2423

881

 

4861

2492

 

7489

290

 

9323

3013

2659

110

 

5207

251

 

7493

5249

 

9443

397

2831

105

 

5297

(12030)

 

7651

(8000)

 

9589

370

2897

9715

 

5359

(12069)

 

7909

2174

 

9743

125

2987

123

 

5371

388

 

7913

125

 

9833

253

3061

(17007)

 

5417

175

 

7921

156

 

9931

496

3289

274

 

5419

170

 

7957

5064

 

9953

205

Table 2.

n = 1 gives a prime for 24 out of the 50 values of odd k < 100.

n = 1 gives a prime for 155 out of the 500 values of odd k < 1000.

n = 1 gives a prime for 1136 out of the 5000 values of odd k < 10000.

n = 1 gives a prime for 9006 out of the 50000 values of odd k < 100000.

 

n = 2 gives a prime for 22 of the 50 values of odd k < 100.

n = 2 gives a prime for 140 of the 500 values of odd k < 1000.

n = 2 gives a prime for 1056 of the 5000 values of odd k < 10000.

n = 2 gives a prime for 8496 of the 50000 values of odd k < 100000.

 

n = 1 and 2 give a prime for 39 of the 50 values of odd k < 100.

n = 1 and 2 give a prime for 265 of the 500 values of odd k < 1000.

n = 1 and 2 give a prime for 2024 of the 5000 values of odd k < 10000.

n = 1 and 2 give a prime for 16484 of the 50000 values of odd k < 100000.

 

n = 1 to 10 give a prime for 49 of the 50 values of odd k < 100.

n = 1 to 10 give a prime for 450 of the 500 values of odd k < 1000.

n = 1 to 10 give a prime for 4150 of the 5000 values of odd k < 10000.

n = 1 to 10 give a prime for 38395 of the 50000 values of odd k < 100000.

 

n = 1 to 100 give a prime for 49 of the 50 values of odd k < 100.

n = 1 to 100 give a prime for 494 of the 500 values of odd k < 1000.

n = 1 to 100 give a prime for 4896 of the 5000 values of odd k < 10000.

n = 1 to 100 give a prime for 48706 of the 50000 values of odd k < 100000.

 

n = 1 to 1000 give a prime for 50 of the 50 values of odd k < 100.

n = 1 to 1000 give a prime for 498 of the 500 values of odd k < 1000.

n = 1 to 1000 give a prime for 4975 of the 5000 values of odd k < 10000.

n = 1 to 1000 give a prime for 49753 of the 50000 values of odd k < 100000.

 

A Sierpinski number is an odd number k such that k.2n +1 is composite for all n 1. Sierpinski proved that the set of Sierpinski numbers is infinite, but the smallest examples he provided were of 18 digits. The Sierpinski Problem is the task of finding k0 - the smallest Sierpinski number. In his proof, Sierpinski used a covering set for each number, i.e. a finite set of primes such that every

k.2n +1 is divisible by at least one of the set. The smallest Sierpinski number known is k = 78557, with covering set {3,5,7,13,19,37,73}, though the Sierpinski number k = 271129 has the shortest covering set {3,5,7,13,17,241}, which has been proved to be the unique shortest possible. In attempting to find k0 , which may or may not be 78557, it is of particular interest to identify, for each odd k, values for which there are no primes for small n, and for each of these to keep raising the search limit on n until a prime is found.

 

The following is a list of 247 odd k < 100000 for which there is no prime for n 1000, giving the lowest value of n giving a prime, or the search limit. Note that the search uses trial division to remove as many values of n as possible from consideration, and so a search limit for a given prime is not necessarily a "round" number.

k

n

 

k

n

 

k

n

383

6393

 

10223

(8000)

 

20851

(8000)

881

1027

 

10583

2689

 

21143

1061

1643

1465

 

10967

2719

 

21167

6095

2897

9715

 

11027

1075

 

21181

(12091)

3061

(17007)

 

11479

1702

 

21901

1540

3443

3137

 

12395

1111

 

22699

(20133)

3829

1230

 

12527

2435

 

22727

1371

4847

(12062)

 

13007

1655

 

22951

1344

4861

2492

 

13787

(8000)

 

23701

1780

5297

(12030)

 

14027

(8000)

 

23779

5234

5359

(12069)

 

16519

3434

 

24151

2508

5897

(20170)

 

16817

(8000)

 

24737

(8000)

6319

4606

 

16987

2748

 

24769

1514

6379

1014

 

17437

1812

 

24977

1079

7013

(24160)

 

17597

3799

 

25171

2456

7493

5249

 

17629

1094

 

25339

4438

7651

(8000)

 

17701

2700

 

25343

1989

7909

2174

 

18107

(12278)

 

25819

(12001)

7957

5064

 

18203

6141

 

25861

4848

8119

1162

 

19021

2608

 

26269

1086

8269

1150

 

19249

(18157)

 

27653

(12344)

8423

(8000)

       

27923

(8000)

8543

5793

 

40547

(8000)

 

28433

(12072)

8929

1966

 

40553

1077

 

29629

1498

9323

3013

 

40571

1673

     
     

41809

1402

 

50693

(8000)

30091

2184

 

42257

2667

 

51617

2675

31951

3084

 

42409

1506

 

51917

(8000)

32161

(8000)

 

43429

4290

 

52771

(8000)

32393

4365

 

43471

1508

 

52909

3518

32731

1720

 

44131

(8000)

 

53941

(8000)

33661

(8000)

 

44629

1270

 

54001

(12115)

34037

1671

 

44903

(8000)

 

54739

(8000)

34565

3361

 

45713

1229

 

54767

(8000)

34711

(8000)

 

45737

2375

 

55459

(8000)

34999

(12273)

 

46157

(12046)

 

56543

2501

35987

2795

 

46159

4790

 

56731

1172

36781

4824

 

46187

(8000)

 

56867

1127

36983

(8000)

 

46403

3057

 

57467

1259

37561

(8000)

 

46471

(8000)

 

57503

5697

38029

2778

 

47179

2918

 

57949

1058

39079

(12249)

 

47897

(8000)

 

58243

1136

39241

1120

 

47911

5568

 

59569

(8000)

39781

(8000)

 

48091

1476

     
     

48323

1369

 

80419

1166

60443

(12260)

 

48833

(8000)

 

80839

(4397)

60541

(8000)

 

49219

(8000)

 

81091

(4631)

60737

1411

       

81269

(4342)

60829

6398

 

70261

3048

 

81857

1399

61519

1290

 

71417

(8000)

 

81871

1420

62093

(12016)

 

71671

(8000)

 

81919

(4817)

62761

(8000)

 

71869

5130

 

82267

2904

63017

(8000)

 

72197

2171

 

82283

2469

63379

2070

 

73189

4278

 

82549

(4349)

64007

(8000)

 

73253

6889

 

82841

1037

64039

2246

 

73849

1202

 

82907

1475

65057

(8000)

 

74191

(8000)

 

84409

(4349)

65477

5887

 

74221

4188

 

84887

1087

65539

1822

 

74269

(8000)

 

85013

(4352)

65567

(20154)

 

74959

4274

 

85711

(4343)

65623

1746

 

75841

(12211)

 

86701

(4375)

65791

2760

 

76261

2156

 

86747

(4346)

65971

1224

 

76759

(8000)

 

86761

3896

67193

(8000)

 

76969

3702

 

86869

(4521)

67607

(18170)

 

77267

4159

 

87469

2110

67759

(8000)

 

77341

5076

 

87743

(4352)

67831

1720

 

77521

3336

 

88007

2843

67913

5773

 

77899

(12209)

 

88157

1063

68393

1901

 

78181

(8000)

 

88549

(4401)

69107

(8000)

 

78557

-------

 

89003

1285

69109

(12021)

 

79309

(5221)

 

89059

(4433)

     

79817

(4430)

 

89225

(4384)

     

79819

1678

 

89521

1564

     

79879

1098

 

89537

1203

               

90019

3470

 

93331

(4463)

 

97621

1820

90047

1403

 

93443

1277

 

97697

2139

90527

(4390)

 

93593

3597

 

97789

1102

90529

2518

 

93617

(4570)

 

98327

2911

90949

2254

 

94069

(4429)

 

98431

(4327)

91291

3432

 

94373

(4420)

 

98461

1892

91399

1746

 

94639

2654

 

98723

1681

91549

(4445)

 

95791

1088

 

98749

(4329)

92119

(4521)

 

96409

1426

 

99557

2931

92567

(4366)

 

96983

(4344)

 

99587

(4394)

92749

1138

 

97555

(4355)

 

99739

(4349)

           

99769

1042

Table 3.

Counts for surviving k values in steps of 10000 are:-

 

 

total

n 1000 :

25, 21, 24, 18, 25, 18, 26, 26, 30, 34

247

n 2000 :

18, 15, 14, 15, 16, 13, 19, 23, 20, 23

176

n 3000 :

16, 9, 12, 12, 13, 11, 16, 21, 16, 17

143

n 4000 :

14, 7, 12, 10, 12, 10, 16, 18, 15, 14

128

 

With direct reference to the Sierpinski Problem, only 178 odd k < 78557 survive with no primes of the form k.2n + 1 for n 1000, and this drops to 95 for n 4000. With further searches concentrated on these values, currently only 69 odd k < 78557 remain unaccounted for, the smallest being 3061. Therefore we can say that 3061 k0 78557.

For each of the values of k > 78557 given in Table 3, only the lowest value of n giving a prime, if known, is listed. Since the search was pushed at least to n 4000 for each of these, the following large primes were discovered with n > 2000, of which 7 have more than 1000 digits.

k

n

79819

3598

81871

2164, 2956

82267

2904

82283

2469

86761

3896

87469

2110

88007

2843, 2915

90019

3470

90529

2518

90949

2254

91291

3432, 3672

93443

3633

93593

3597

94639

2654

97697

2139

98327

2911

98723

2245

99557

2931

 

There remain 31odd k in the higher range for which an associated Robinson prime is not known.

As suggested by the above, I have concentrated mainly in the range 78558 < k < 100000. As part of this, I have located all primes of the form k.2n + 1 for 1001 n 2000. I then extended this search to cover the range 70000 < k < 78556. Both ranges are detailed below.

range 1 : 78558 < k < 100000

range 2 : 70000 < k < 78556

range of n

range 1 count

range 2 count

1001 - 1100

2856

1153

1101 - 1200

2715

1066

1201 - 1300

2435

972

1301 - 1400

2204

894

1401 - 1500

2144

839

1501 - 1600

1953

803

1601 - 1700

1875

744

1701 - 1800

1706

677

1801 - 1900

1610

626

1901 - 2000

1596

622

totals

21094

8396

This gives at total of 29490 primes in the combined range.

The following three Fermat divisors that fall within this range were rediscovered and verified.

82165 * 21084 + 1 divides F1082 ; 79707 * 21231 + 1 divides F1225 ; 98855 * 21851 + 1 divides F1849

The highest number of primes for a particular k in the combined search range 70000 < k < 100000, and for 1001 n 2000, is 12. This occurs at k = 70365. A count of 11 is achieved for the k values 70653, 73413, 84435, 89595 and 91575.

 

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