Counting Robinson Primes & Testing as divisors of Generalised Fermat numbers

Joseph McLean

Numbers of the form k*2ⁿ +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 re-sieved repeatedly. This substantial overhead may be reduced by using readily-available 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⁵. Currently, this k-range 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 high-level view of the k-range in question is given by the following :

Column 2 in the above table may be broken down as follows :

Column 2 in this table may be even further broken down as follows :

It is widely known that Fermat numbers have no algebraic factors and that any divisor must be of the form k.2ⁿ + 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 non-trivial 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ⁿ + 1 in the range 1 £ n £ 100 initially. Within this range, there are 3605 instances of k.2ⁿ + 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² and GF(41,1) = 29²).

Possible divisors with k = 1 are obviously the prime Fermat numbers themselves. In fact,

2¹ + 1 divides 31 GFs out of a possible 87, 2² + 1 divides 53, 2⁴ + 1 divides 77, and 2⁸ + 1 and 2¹⁶ + 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⁸ + 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ⁿ + 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:

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 :

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⁵, 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⁵ 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 :