By Wilfrid Keller
Seelhoff's goal had been the discovery of some factor of a Fermat number Fm, which is of the form Fm = 22m + 1. The second largest prime in the list, 2748779069441 = 5 · 239 + 1, in fact proved to divide the Fermat number F36. At this time, it was only the 7th known factor of this kind and clearly the largest of them. Curiously, Seelhoff had the prime 13631489 = 13 · 220 + 1 in his list, without realizing that it also divided a Fermat number, in this case F18. This divisibility was finally established by A. E. Western in 1903.
Cunningham and Western 1904. In 1904, Allan J. C. Cunningham and A. E. Western jointly published a note in the Proceedings of the London Mathematical Society presenting seven new factors of Fermat numbers which they basically found in collaborative work during the period from 1899 to 1903. The largest of these was the factor 6597069766657 = 3 · 241 + 1 of F38. In their note the authors asserted that beyond the four known prime factors p < 106 no other factor existed in that range.
This was the result of examining the complete table of 298 primes p = k · 2n + 1 of that size with odd k and n ≥ 9 they had previously produced. Probably in a nearby period, two additional tables of primes p of that form were prepared, including a selection of 264 primes in the range 106 < p < 107 and 158 primes in the range 107 < p < 108, making a total of 720 primes of the form k · 2n + 1. In any case, all the newly discovered factors, except the largest one, are contained in some of these tables.
Only in 1927, A. J. C. Cunningham included the above tables (mostly prepared by Western, according to him) in a book entitled Quadratic and Linear Tables. In the Introduction, Cunningham emphasizes the motivation for collecting that particular type of primes:
These Tables are useful in the search for divisors p of Fermat's Numbers Fm, and were in fact originally prepared for, and used for, that purpose.It should be remarked that only Cunningham and Western used a different notation for the expression k · 2n + 1 than that introduced by Seelhoff.
Kraitchik 1926. In his book Théorie des nombres II: Analyse indéterminée du second degré et factorisation, published in Paris in 1926, Maurice Kraitchik included a substantial table of primes of the form p = k · 2n + 1, again bound to be “large” in some way. The precise limitation was set to be 108 < p < 1012, with k restricted to k < 1000. In this range, there exist 579 primes of the given form. Of these, 572 were correctly listed, by increasing size. For the 7 missing primes, an erroneous divisor had been given in each case.
One prime of the list, 1214251009 = 579 · 221 + 1, turned out to divide the Fermat number F15, a relation discovered by Kraitchik in 1925. This was now the 16th known divisor of a Fermat number. Two of these were beyond Kraitchik's range, a consequence of the fact that the smallest possible multipliers k = 3 and k = 5 had been searched particularly extensively (a most reasonable decision, as we currently know). The largest factor known at this time was indeed 188894659314785808547841 = 5 · 275 + 1, shown by J. C. Morehead to divide F73, in 1905 PDF.
Robinson 1958. The paper by Raphael M. Robinson, A report on primes of the form k · 2n + 1 and on factors of Fermat numbers PDF, published in 1958, marked a milestone in the search we are considering, as a new era was started with the technical equipment used:
This note is a report on some calculations carried out during 1956 and 1957 on the SWAC, a high-speed computer located on the Los Angeles campus of the University of California […].More importantly, the subject was clearly described and a methodology established which is basically still in use today:
Since every odd number N > 1 can be put in the form N = k · 2n + l, with k odd, k > 0, and n > 0, the only meaning which can be attached to describing a number as being of this form is a rather vague one, namely that the value of k involved is relatively small. In the course of our computation, all of these numbers with k < 100 and n < 512 were tested for primeness, as well as some numbers lying outside of this range.A suitable form of the indicated theorem reads:A preliminary sieve routine was used to look for small factors of N. […] If no small factor was found, the number was tested for primeness using a theorem stated by Proth in 1878 […]. The only cases to which the test does not apply are those where n is very small, and here no test is needed.
Proth's Theorem. Let N = k · 2n + 1 with 2n > k. If there is an integer a such that a(N − 1)/2 = − 1 (mod N), then N is prime.
The test is simple, in practice the difficulty is multiplying the large numbers involved. Incidentally, primes of the considered form satisfying the condition 2n > k of the theorem are now usually called Proth primes.
In Table 1 of Robinson's paper, primes k · 2n + 1 are listed for odd k < 100 and for all 1 ≤ n < 512. Among a few larger primes, the table included the 587-digit prime 5 · 21947 + 1 which divides the Fermat number F1945. This was the largest known Fermat divisor for about 22 years. In addition, the prime itself was the fourth largest prime known at the time, only surpassed by three Mersenne primes.
Individual searchers 1977-1985. After a silence of almost two decades, several papers were being published in the journal Mathematics of Computation reporting on successive extensions of Robinson's table. In each case, at least one Fermat factor was contained in the respective table.
G. Matthew and H. C. Williams (1977), Some new primes of the form k · 2n + 1 PDF. Table extension to k < 130, n ≤ 1000 (two Fermat factors).
R. Baillie (1979), New primes of the form k · 2n + 1 PDF. Table extension to k < 150, n ≤ 1500 (three Fermat factors).
G. V. Cormack and H. C. Williams (1980), Some very large primes of the form k · 2n + 1 PDF. Table extension for k < 30, n ≤ 4000, at least (four Fermat factors).
W. Keller (1983), Factors of Fermat numbers and large primes of the form k · 2n + 1 PDF. Table extension to k < 20, n ≤ 8500, and to 20 < k < 200, n ≤ 4000 (two Fermat factors).
A further extension by H. Suyama (1985) was published in a Japanese journal and covered 200 < k < 500 to at least n ≤ 2200 (one Fermat factor).
In preparation of a (finally unpublished) sequel paper to that of 1983, the overall limits of the list of primes maintained by the author were extended in 1991 as follows.
| Interval for k | Limit for n |
| 1 < k < 32 | 15000 |
| 32 < k < 64 | 12000 |
| 64 < k < 120 | 8000 |
| 120 < k < 200 | 4000 |
| 200 < k < 500 | 2500 |
| 500 < k < 1200 | 1000 |
The list had a total of 8963 primes, including 36 miscellaneous primes beyond these limits.
Interlude on generalized Fermat numbers. In 1969, Hans Riesel called attention to the fact that in analogy to the Fermat numbers Fm = 22m + 1, numbers Fm(a) = a2m + 1 with an even base a have many similar characteristics. Specifically, they have no algebraic factors, they may be prime, and it is easy to prove primality. Moreover, all prime factors must be of the form k · 2n + 1, which we are considering here. For the first time, Riesel studied the explicit factorizations for two of these sequences, Fm(6) and Fm(10).
In an article of the Journal of Recreational Mathematics, Harvey Dubner independently introduced such “generalized Fermat numbers” (GFNs) in 1986 with the purpose of using them for generating large primes. But he was not aware of the connection. During a discussion about Fermat numbers, Dubner was pointed to it by the present author in September 1992. This prompted him to start a systematic factor search, including other bases than a = 6 and a = 10, which finally resulted in an extensive cooperation. Dubner sketched a theory about the statistical distribution of such factors and decided to write a paper about it, kindly inviting me to be his co-author. The paper, which included factor tables of Fm(a) for a = 6, 10 and 12, was submitted in August 1993, and finally published in January 1995.
Harvey Dubner and Wilfrid Keller, Factors of generalized Fermat numbers, Math. Comp. 64 (1995), 397-405. PDF
Maintaining a database 1992. During this investigation (September 1992 to August 1993) the existing prime list was considerably expanded by the two authors, and enriched with large primes supplied by Jeff Young, with the following result.
| Interval for k | Limit for n |
| 1 < k < 32 | 40000 |
| 32 < k < 64 | 12000 |
| 64 < k < 120 | 10000 |
| 120 < k < 220 | 8000 |
| 220 < k < 1200 | 4000 |
| 1200 < k < 2246 | 2000 |
| 2246 < k < 20000 | 1200 |
Regarding the generalized Fermat numbers, we experienced a remarkable coincidence. We surprisingly learned that Hans Riesel, assisted by a younger colleague, had started a similar, but more encompassing research just while we were finishing our paper. They considered the more general class of numbers Fm(a,b) = a2m + b2m, which again have the same divisibility properties. Without knowing of our work (but of our interest in Fermat numbers), Riesel sent us a rough manuscript in February 1994. The computations had begun only a few months earlier, as he had reported at a Conference in Vancouver, Canada, in August 1993. After a number of modifications, the evolving paper, along with an extensive table supplement, was submitted in May 1996 and published in January 1998. Curiously, both our papers had exactly the same title: Factors of Generalized Fermat Numbers.
Anders Björn and Hans Riesel, Factors of generalized Fermat numbers, Math. Comp. 67 (1998), 441-446, with Tables supplement, 49 pages. PDF
For additional details of that publication, please see this report. Also, let it be said that the two GFN papers do not exactly reflect who had actually determined which of the individual factors. In particular, all factors from “Dubner and Keller” were later included in “Björn and Riesel”, and many other factors were provided by Dubner or Keller to the “Björn and Riesel” supplement. However, based on innumerable emails and various intermediate drafts, the correct “ownership” could restrospectively be established for all known factors of numbers Fm(a) with a = 3, 5, 6, 7, 10, 11, 12.
As far as primes k · 2n + 1 are concerned, from August 1993 to the end of 1997 the prime number database received contributions from Björn and Riesel, Young, Keller, and Joe McLean, leading to the following general status, whose gradual growing is documented here along with pertinent references.
| Interval for k | Limit for n |
| 3 ≤ k < 14 | 200000 |
| 14 < k < 32 | 100000 |
| 32 < k < 64 | 50000 |
| 64 < k < 256 | 20000 |
| 256 < k < 1200 | 10000 |
| 1200 < k < 10000 | 5000 |
| 10000 < k < 40000 | 3000 |
| 40000 < k < 100000 | 2000 |
Gallot and Ballinger 1998. In May 1997, Yves Gallot informed the present author that he wrote a program, called Proth.exe, designed to search for primes of the form k · 2n + 1 and to ultimately find big factors of Fermat numbers. He added:
I asked Chris Caldwell where I can find a list of factors of Fermat numbers and a list of numbers of the form k ·2n + 1 that have been tested for primality and he gave me your name.The provided information formed the base for Gallot to extensively test his program and to advance to new regions. The program was publicly released and subsequently improved and extended to cover other types of numbers and to include divisibility tests for certain GFNs. It was soon also used by others to contribute to the ongoing search. This made obvious the need once expressed by Harvey Dubner about the tabulation of primes k ·2n + 1, particularly considering their application to Fermat numbers and generalized Fermat numbers:
With the large and expanding number of high-performance workstations and PCs that are available to the academic community, it seems that a world-wide organized effort to expand this list would be a logical project.The enterprise of organizing such a cooperative effort was undertaken by one of the participants, Ray Ballinger. He created a website named Proth Search Page, to serve the Proth Search project. It turned operational just at the beginning of 1998 and was introduced as follows:
Yves Gallot wrote an excellent Windows program which makes it easy for anyone to find record size or otherwise interesting primes, but this creates a problem: without a coordinated effort, many of us were be searching the same ranges of numbers for primes! Some spent hundreds of hours checking ranges that were already known to be barren. So I have begun this page in order to reduce this unnecessary duplication. Please join us in the search!The website provided a means to interactively access a “reserve or submit a range” page, also summarizing which of the predetermined blocks had already been done. The produced results were incorporated into the lists and tables originally shared by the present author with Gallot, which henceforth were being updated within this framework. Starting in 2005, Ballinger was assisted in his maintenance work by Mark Rodenkirch, who gradually took the entire burden on himself. One substantial change of this period was to recommend more advanced programs for the computations. Proth was replaced by LLR (developed by Jean Penné) for prime proving, and PFGW, whose ability to test for GFN divisibilities was introduced by Jim Fougeron.
PrimeGrid 2008. Also in 2005, a so-called Volunteer Computing project with the name PrimeGrid was set up by Rytis Slatkevičius. This is a software managed distributed effort, which over the years incorporated different number theory subprojects. Thus, a “Proth Prime Search” subproject was started in February 2008, to supplement and extend Ballinger's Proth Search effort, with the perspective to finally supplanting it. Soon afterwards Mark Rodenkirch announced “an agreement with the PrimeGrid project for the searching of Proth primes”. This concerned the computational side. On the other hand, the purely documentary part, in charge of this author, was adapted with the kind support of John Blazek, a leading volunteer administrator of PrimeGrid. Near the end of 2015, the reservation system of the original Proth Search was virtually shut down, leaving the continuing search for primes of the form k ·2n + 1 entirely to PrimeGrid.
The comprehensive documentary part was transferred to a New Proth Search Page. Although the website is not dealing with the “search” as such, it gives an up-to-date account of its impressive progress. The possibly misleading name was actually preserved to honour Ray Ballinger's memory.
This report would not be complete without mentioning a “basic” table of primes generated by an independent
researcher. Joe McLean accomplished the enumeration
of all primes k ·2n + 1 for k < 100000 and n ≤ 10000 in 2005. The
list and all partial counts have thoroughly been verified by Keller in 2017, resulting in a total of 930550 primes.
______________________________
Provisional draft of 15 February 2022
Questions, corrections or suggestions are welcome at
W.K.