Enumeration of Proth Primes

Proth primes, or Robinson primes as I prefer to call them, are primes of the form k*2n +1 where k is odd. Bearing in mind that all primes can be expressed in this form, it is obvious that there is more to this than meets the eye.

Firstly, when k < 2n, there is a very efficient algorithm for proving primality, and secondly, divisors of generalised Fermat numbers GF(a,m) must be of the form k*2n + 1 for some n greater than m.

It is therefore useful to have readily available lists of such primes for small k. In this article, we are interested in enumerating Proth primes for k < 105. Additional benefits include the production of a large body of sample primes for whatever reason, including divisibility properties and statistical analysis.

For n 1000, the frequency of occurrence of primes is very high, and all kinds of analysis can be performed. Counts of Proth primes for each n may be found in robstats.txt. Counts of prime for each k may be found in robcount.txt (N.B. leaving 247 values of k with no associated Proth prime in this range). For each k, if we count the number of Proth primes in the range, the counts range from 0 to 48, i.e. there is a value of k which produces 48 Proth primes with n 1000. Counts of counts may be found in robsumm.txt. I have also previously checked the primes in this range as divisors of generalised Fermat numbers with non-prime-power bases less than 100.

A detailed breakdown of the number of Proth primes n this first range is as follows:

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

100

31947

29840

29382

29038

28671

28460

27939

27932

27950

27895

289054

200

9100

9002

9061

8889

8946

8960

9053

8860

8796

8930

89597

300

5487

5473

5405

5459

5576

5495

5516

5534

5499

5408

54852

400

3998

4035

4026

3949

3772

3883

3947

4101

3904

3970

39585

500

3209

3183

3052

3132

3137

3057

3046

3210

3206

3141

31373

600

2604

2604

2472

2495

2602

2661

2580

2654

2505

2568

25745

700

2171

2168

2178

2162

2169

2134

2107

2152

2158

2160

21559

800

1896

1872

1838

1802

1873

1792

1903

1899

1811

1860

18546

900

1659

1649

1692

1705

1619

1642

1622

1658

1615

1711

16572

1000

1405

1475

1496

1517

1544

1522

1523

1545

1583

1524

15134

total

63476

61301

60602

60148

59909

59606

59236

59545

59027

59167

602017

Lists of these primes, though large, are available on request.

Wilfrid Keller has for many years co-ordinated the search for divisors of generalised Fermat numbers, and as part of this has kept statistics on the numbers of Proth primes for k < 100000, and higher exponents n. However, this data has never been made available for general consumption. This article is an attempt to provide detailed counts for higher exponents, and the aim is to keep it as up-to-date as possible.

The following counts are provided in ranges of n up to whole thousands, with subdivisions at each hundred.

The next table is for the range 1001 n 2000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

1100

1384

1427

1389

1348

1416

1363

1295

1330

1313

1366

13631

1200

1307

1237

1226

1268

1243

1223

1219

1264

1243

1274

12504

1300

1100

1090

1090

1102

1150

1191

1141

1154

1070

1183

11271

1400

1053

1065

1040

1096

1101

1027

1018

1033

1058

1007

10498

1500

1015

1000

1027

1050

1023

1030

970

979

997

1007

10098

1600

950

935

944

885

879

930

940

945

903

908

9219

1700

848

857

826

853

879

868

852

861

892

866

8602

1800

771

852

796

766

839

802

836

802

790

791

8045

1900

749

783

772

755

763

777

746

733

734

769

7581

2000

724

732

713

741

741

738

699

738

767

713

7306

total

9901

9978

9823

9864

10034

9949

9716

9839

9767

9884

98755

The next table is for the range 2001 n 3000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

2100

668

648

676

703

672

755

703

683

719

656

6883

2200

650

675

686

685

627

685

650

701

625

639

6623

2300

669

630

652

596

622

630

636

583

598

626

6242

2400

598

582

621

619

575

569

604

567

572

592

5899

2500

580

580

571

570

599

571

567

563

559

586

5746

2600

529

600

589

535

559

528

598

595

551

518

5602

2700

565

510

533

537

528

527

581

544

525

561

5411

2800

557

531

531

544

528

545

503

571

522

506

5338

2900

486

499

519

524

508

520

512

482

527

490

5067

3000

519

488

507

451

487

481

454

478

457

432

4754

total

5821

5743

5885

5764

5705

5811

5808

5767

5655

5606

57565

The next table is for the range 3001 n 4000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

3100

458

473

450

439

457

469

445

461

448

460

4560

3200

473

461

467

461

469

460

464

478

439

455

4627

3300

425

454

444

435

421

446

444

416

444

427

4356

3400

446

449

462

457

463

401

416

433

451

449

4427

3500

438

416

436

418

452

403

412

411

405

438

4229

3600

396

407

429

379

409

396

359

394

414

378

3961

3700

362

422

400

382

408

449

418

425

385

401

4052

3800

390

386

410

372

408

407

384

400

365

436

3958

3900

356

379

401

365

386

308

373

361

408

396

3733

4000

366

338

380

340

381

389

349

354

352

345

3594

total

4110

4185

4279

4048

4254

4128

4064

4133

4111

4185

41497

The next table is for the range 4001 n 5000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

4100

351

347

348

370

368

339

375

391

370

331

3590

4200

330

368

325

360

369

315

357

364

338

329

3455

4300

347

313

334

297

339

315

333

323

350

349

3300

4400

326

338

322

306

296

339

317

343

346

317

3250

4500

329

315

313

343

293

329

336

325

304

335

3222

4600

348

303

293

335

325

292

314

324

305

307

3146

4700

278

293

289

313

312

290

299

295

324

329

3022

4800

351

300

296

292

271

296

320

286

292

306

3010

4900

281

281

289

299

288

282

271

279

327

273

2870

5000

290

289

276

275

279

285

301

266

286

295

2842

total

3231

3147

3085

3190

3140

3082

3223

3196

3242

3171

31707

The next table is for the range 5001 n 6000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

5100

256

283

285

315

269

288

295

262

280

294

2827

5200

288

277

262

265

283

291

302

303

235

298

2804

5300

276

283

279

249

286

297

282

290

285

252

2779

5400

265

278

298

280

247

291

270

258

249

270

2706

5500

223

246

282

285

241

261

288

290

243

267

2626

5600

224

269

238

255

257

267

234

248

250

255

2497

5700

268

269

235

246

272

258

280

266

249

249

2592

5800

241

225

261

225

233

248

271

249

251

253

2457

5900

250

240

238

243

270

251

217

229

212

228

2378

6000

249

240

252

244

241

244

257

252

245

258

2482

total

2540

2610

2630

2607

2599

2696

2696

2647

2499

2624

26148

The next table is for the range 6001 n 7000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

6100

223

245

243

236

226

252

237

232

214

246

2354

6200

216

236

259

233

253

254

235

261

247

227

2421

6300

239

223

219

223

240

232

207

220

243

241

2287

6400

244

235

234

212

235

222

215

213

196

241

2247

6500

228

239

204

216

238

229

198

237

230

236

2255

6600

231

238

221

237

198

215

202

203

248

193

2186

6700

214

229

242

205

224

201

236

215

207

191

2164

6800

191

209

184

214

217

172

214

220

179

189

1989

6900

229

216

197

195

208

185

200

194

200

209

2033

7000

222

194

201

182

213

206

205

219

194

195

2031

total

2237

2264

2204

2153

2252

2168

2149

2214

2158

2168

21967

The next table is for the range 7001 n 8000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

7100

213

241

163

193

184

195

185

204

186

225

1989

7200

182

215

201

175

202

189

187

198

211

173

1933

7300

183

218

185

177

204

187

170

173

189

177

1863

7400

181

188

201

202

198

234

210

214

207

196

2031

7500

196

191

189

178

199

201

199

194

193

230

1970

7600

224

208

194

170

210

195

167

188

196

173

1925

7700

184

203

185

163

199

184

188

212

190

184

1892

7800

177

205

171

189

169

181

185

182

169

160

1788

7900

179

208

178

171

180

186

176

195

172

185

1830

8000

181

182

159

172

183

174

181

199

177

172

1780

total

1900

2059

1826

1790

1928

1926

1848

1959

1890

1875

19001

The next table is for the range 8001 n 9000.

n \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

8100

187

191

183

161

181

188

177

185

158

181

1792

8200

170

161

162

157

175

177

174

183

151

184

1694

8300

165

162

158

162

156

173

164

186

173

164

1663

8400

163

143

172

182

164

158

185

166

176

172

1681

8500

153

179

149

172

177

174

167

145

188

168

1672

8600

158

169

156

162

169

160

167

169

186

163

1659

8700

153

185

172

174

158

184

166

178

178

167

1715

8800

175

163

165

143

151

167

176

153

162

146

1601

8900

153

185

147

152

154

181

163

156

145

166

1602

9000

158

165

175

141

162

174

164

148

179

143

1609

total

1635

1703

1639

1606

1647

1736

1703

1669

1696

1654

16688

The next table completes the search to n = 10000.

N \ k

<10000

<20000

<30000

<40000

<50000

<60000

<70000

<80000

<90000

<100000

total

9100

157

161

159

163

156

159

144

181

160

152

1592

9200

170

148

167

176

174

143

165

180

148

150

1621

9300

142

153

148

154

162

151

188

162

159

161

1580

9400

159

138

150

166

142

157

142

140

147

150

1491

9500

158

157

156

150

147

146

178

167

159

139

1557

9600

152

130

154

134

164

146

146

173

154

131

1484

9700

168

135

138

133

146

150

152

165

137

140

1464

9800

164

155

167

151

166

127

129

152

157

156

1524

9900

150

143

136

129

141

144

143

147

149

163

1445

10000

143

137

153

139

140

143

148

173

143

126

1445

total

1563

1457

1528

1495

1538

1466

1535

1640

1513

1468

15203

The grand totals for 1 n 10000 are as follows.

Total

96414

94447

93501

92665

93006

92568

91978

92609

91558

91802

930548

Some subranges for higher exponents have also been searched but it seems inappropriate to list isolated counts.

I would be happy to forward files to anyone who would like to obtain the lists of primes generated during this search. With the exception of the n 1000 range, the file sizes are not particularly large.

I have previously listed the divisors of generalised Fermat numbers with square-free bases less than 100, amongst the range n 1000. I am in the process of pushing this search to higher values of n. The current position of this search can always be found by checking the results file. This is ongoing and will always drag behind the enumeration to a degree.

 

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