Enumeration of Proth Primes

Proth primes, or Robinson primes as I prefer to call them, are primes of the form k*2ⁿ +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 < 2ⁿ, 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*2ⁿ + 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 < 10⁵. 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