Counting Robinson Primes & Testing as divisors of Generalised Fermat numbers
Joseph McLean
Numbers of the form k*2^{n} +1 are routinely tested as factors of generalised Fermat numbers. However, it has often been the case in the past that the primality of the divisors has not been fully verified before the division test has been made, with survival against a restricted prime sieve deemed sufficient in order to reduce processing time. This has meant that as more general Fermat numbers have been targeted, the same ranges have been resieved repeatedly. This substantial overhead may be reduced by using readilyavailable lists of Robinson primes over recognised ranges. In recent years, Wilfrid Keller has been collating such lists with the help of a number of contributors. The volume of data is extensive and not suitable in its standard form to appear in print. However, a detailed analysis can be obtained by counting the number of primes in particular ranges, concentrating either on k or n as the main variable.
This account will concentrate entirely on the range k < 10^{5}. Currently, this krange has been checked for all n £ 4000, although this limit on n has been greatly exceeded for particular values of k, for instance very small k < 300, certain other k with either very low or very high Nash weight, and other values for a number of reasons. However, for the scope of this article, we are only interested in complete ranges. As ever, k is assumed to be odd.
A highlevel view of the krange in question is given by the following :
k range 
1 £ n £ 1000 
1001 £ n £ 2000 
2001 £ n £ 3000 
3001 £ n £ 4000 
19999 
63476 
9901 
5821 
4110 
1000119999 
61301 
9978 
5743 
4185 
2000129999 
60602 
9823 
5885 
4278 
3000139999 
60148 
9864 
5764 
4048 
4000149999 
59909 
10034 
5705 
4254 
5000159999 
59606 
9949 
5811 
4128 
6000169999 
59236 
9716 
5808 
4064 
7000179999 
59545 
9839 
5767 
4133 
8000189999 
59027 
9767 
5655 
4111 
9000199999 
59167 
9884 
5606 
4185 
totals 
98755 
57565 
41496 
Column 2 in the above table may be broken down as follows :
£ 100 
£ 200 
£ 300 
£ 400 
£ 500 
£ 600 
£ 700 
£ 800 
£ 900 
£ 1000 
totals 

<10K 
9100 
5487 
3998 
3209 
2604 
2171 
1896 
1659 
1405 

<20K 
9002 
5473 
4035 
3183 
2604 
2168 
1872 
1649 
1475 

<30K 
9061 
5405 
4026 
3052 
2472 
2178 
1838 
1692 
1496 

<40K 
8889 
5459 
3949 
3132 
2495 
2162 
1802 
1705 
1517 

<50K 
8946 
5576 
3772 
3137 
2602 
2169 
1873 
1619 
1544 

<60K 
8960 
5495 
3883 
3057 
2661 
2134 
1792 
1642 
1522 

<70K 
9053 
5516 
3947 
3046 
2580 
2107 
1903 
1622 
1523 

<80K 
8860 
5534 
4101 
3210 
2654 
2152 
1899 
1658 
1545 

<90K 
8796 
5499 
3904 
3206 
2505 
2158 
1811 
1615 
1583 

<100K 
8930 
5408 
3970 
3141 
2568 
2160 
1860 
1711 
1524 

Totals 
89597 
54852 
39585 
31373 
25745 
21559 
18546 
16572 
15134 
602017 
Column 2 in this table may be even further broken down as follows :
110 
1120 
2130 
3140 
4150 
5160 
6170 
7180 
8190 
91100 
totals 

<10K 
8632 
5308 
3840 
3116 
2488 
2152 
1913 
1640 
1510 
1348 

<20K 
7623 
4869 
3733 
2948 
2398 
2112 
1845 
1601 
1446 
1265 

<30K 
7296 
4847 
3678 
2996 
2383 
2064 
1756 
1635 
1439 
1288 

<40K 
7147 
4767 
3528 
2865 
2424 
2151 
1850 
1547 
1422 
1337 

<50K 
6994 
4803 
3604 
2799 
2413 
1993 
1764 
1601 
1406 
1294 

<60K 
6953 
4694 
3471 
2864 
2353 
2032 
1808 
1618 
1391 
1276 

<70K 
6783 
4598 
3430 
2818 
2350 
1943 
1730 
1604 
1408 
1275 

<80K 
6799 
4614 
3385 
2791 
2418 
1998 
1703 
1549 
1411 
1264 

<90K 
6674 
4548 
3460 
2763 
2338 
2019 
1827 
1570 
1405 
1346 

<100K 
6687 
4561 
3430 
2781 
2346 
1989 
1770 
1607 
1407 
1317 

totals 
71588 
47609 
35559 
28741 
23911 
20453 
17966 
15972 
14245 
13010 
It is widely known that Fermat numbers have no algebraic factors and that any divisor must be of the form k.2^{n} + 1 where n ³ m + 2. For the more general numbers of the form , suppose that a is itself a power, b^{x} say. Then either x = 2^{r}, in which case , or x is divisible by a odd prime, in which case has a nontrivial algebraic factorisation. The form of any divisors of remains the same as for normal Fermat numbers, with the weakened condition n ³ m + 1. When a is odd, there is also a single, unavoidable algebraic factor 2. Let us define the Generalised Fermat number GF(a,m) to be when a is even and () / 2 when a is odd. We shall use the abbreviation GF to refer to an unspecified example. We will make the restrictions m ³ 0 and 2 £ a £ 100. We will also ignore any value of a that is a power. This involves the set {4,8,9,16,25,27,32,36,49,64,81,100}, and leaves 87 bases to check. In the case m = 0, which appears for completeness only, we shall remove all powers of 2 from the GF. Also, it is obvious that no two GFs to the same base can have a common factor.
We shall consider divisors k.2^{n} + 1 in the range 1 £ n £ 100 initially. Within this range, there are 3605 instances of k.2^{n} + 1 dividing a Generalised Fermat number. This includes 64 occurrences of prime GFs, and 2 occurrences of prime power GFs (that is, GF(7,1) = 5^{2} and GF(41,1) = 29^{2}).
Possible divisors with k = 1 are obviously the prime Fermat numbers themselves. In fact,
2^{1} + 1 divides 31 GFs out of a possible 87, 2^{2} + 1 divides 53, 2^{4} + 1 divides 77, and 2^{8} + 1 and 2^{16} + 1 both divide all 87 GFs. The reasoning is as follows: if a º 0 mod p, then º 0 mod p, and if a º ± 1 mod p, then º 1 mod p, and so p cannot divide GF(a,m) in these cases. Thus, if we searched higher, we would find that 2^{8} + 1 did not divide any GF to base 257 or 258. For any other a, if p is a Fermat prime of the form 2^{n} + 1, then Fermat's little theorem gurantees that º  1 mod p for some m < n.
For k = 1 then, there are 31+53+77+87+87 = 335 divisors of GFs. For k < 100, the number of primes in the range and the divisor counts are as follows:
k 
prs 
count 
k 
prs 
count 
k 
prs 
count 
k 
prs 
count 
k 
prs 
count 
1 
5 
335 
21 
9 
67 
41 
3 
6 
61 
4 
4 
81 
16 
23 
3 
11 
272 
23 
8 
22 
43 
8 
16 
63 
16 
14 
83 
2 
1 
5 
10 
163 
25 
9 
23 
45 
8 
9 
65 
10 
11 
85 
10 
17 
7 
9 
126 
27 
17 
48 
47 
0 
0 
67 
7 
11 
87 
8 
5 
9 
15 
152 
29 
10 
33 
49 
7 
9 
69 
8 
6 
89 
6 
6 
11 
8 
54 
31 
3 
12 
51 
12 
22 
71 
9 
13 
91 
1 
2 
13 
6 
45 
33 
10 
24 
53 
7 
12 
73 
9 
8 
93 
11 
6 
15 
12 
59 
35 
11 
25 
55 
6 
7 
75 
15 
19 
95 
12 
11 
17 
4 
18 
37 
11 
35 
57 
14 
20 
77 
5 
6 
97 
5 
5 
19 
3 
12 
39 
18 
30 
59 
4 
7 
79 
3 
1 
99 
16 
17 
There are thus 1849 occurrences of divisors from the 431 primes in the range k < 100.
There are 661 divisors for 100 < k < 1000 from 3150 primes.
There are 573 divisors for 1000 < k < 10000 from 28366 primes.
There are 522 divisors for 10000 < k < 100000 from 257107 primes.
This gives a total of 1849+661+573+522 = 3605 from a total of 289054 primes.
Previous investigations by Keller and Dubner have suggested that the ratio of divisors to bases is inversely proportional to k for a particular n. If we take the average number of divisors as the count of actual divisors divided by the number of primes, then we have
for k = 1, 335 / (5*87) = 0.77 against 1.0000
for k = 3, 272 / (11*87) = 0.284 against 0.3333
for k = 5, 163 / (10*87) = 0.187 against 0.2000
for k = 7, 126 / (9*87) = 0.161 against 0.1429
for k = 9, 152 / (15*87) = 0.1165 against 0.1111
which gives a reasonable correspondence overall.
In terms of the difference between n and m, we have :
n m 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
count 
1827 
881 
461 
212 
97 
58 
34 
17 
5 
8 
2 
1 
0 
2 
ratio 
1.97 
4.09 
7.82 
17.00 
37.16 
62.15 
106 
212 
721 
450 
1802 
3605 
 
1802 
where the ratio is between the total number of divisors and the count, and from which it is possible to infer (ignoring the last few values) that the likelihood that n m = q for some q is inversely proportional to 2^{q}, as has also previously been suggested.
The next step is to consider n from 101 to 1000. Lists of Robinson primes are readily available for k < 10^{5}, so all that is required is to check these lists for factors.
There are 477 divisors for k < 10 from 26 primes
There are 622 divisors for 10 < k < 100 from 275 primes
There are 632 divisors for 100 < k < 1000 from 2830 primes
There are 630 divisors for 1000 < k < 10000 from 28398 primes
There are 552 divisors for 10000 < k < 100000 from 281434 primes
This gives a total of 477+622+632+630+552 = 2913 from 312963 primes.
Combining the previous findings, we have a total of 6518 divisors from 602017 primes in the range 0 < k < 10^{5} and 1 £ n £ 1000. Counts of the number of primes for each n are available, and the full list can be provided on request.
Occurrences of generalised Fermat divisors split by k and n ranges are as follows :
k\n range 
£ 100 
£ 200 
£ 300 
£ 400 
£ 500 
£ 600 
£ 700 
£ 800 
£ 900 
£ 1000 
totals 
<10K 
3083 
658 
505 
342 
242 
174 
139 
130 
121 
50 
5444 
<20K 
166 
50 
25 
15 
17 
11 
10 
10 
5 
7 
316 
<30K 
80 
26 
15 
10 
8 
6 
6 
7 
3 
4 
165 
<40K 
61 
25 
14 
17 
7 
4 
5 
4 
3 
5 
145 
<50K 
48 
14 
10 
2 
6 
7 
5 
2 
3 
5 
102 
<60K 
46 
21 
13 
7 
3 
1 
3 
2 
4 
5 
105 
<70K 
39 
6 
9 
7 
3 
2 
4 
3 
4 
3 
80 
<80K 
20 
4 
6 
7 
5 
2 
1 
1 
4 
1 
51 
<90K 
37 
5 
4 
6 
4 
2 
1 
1 
1 
2 
63 
<100K 
25 
4 
3 
1 
3 
4 
2 
3 
1 
1 
47 
totals 
3605 
813 
604 
414 
298 
213 
176 
163 
149 
83 
6518 