Enumeration of Proth Primes

Joe McLean − April 2005

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 primes 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 with n in 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 316 357 364 338 329 3456
≤ 4300 347 313 334 297 339 315 333 323 350 350 3301
≤ 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 3083 3223 3196 3242 3172   31709

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   92569   91978   92609   91558   91803   930550

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.