* By Wilfrid Keller *

Seelhoff's goal had been the discovery of some factor of a
Fermat number *F _{m}*, which is of the form

**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 · 2^{41} + 1 of *F*_{38}.
In their note the authors asserted that beyond the four known prime factors
*p* < 10^{6} no other factor existed in that range.

This was the result of examining the complete
table of 298 primes *p* = *k* · 2^{n} + 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
10^{6} < *p* < 10^{7} and 158 primes in the range
10^{7} < *p* < 10^{8}, making a total of 720 primes
of the form *k* · 2^{n} + 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 divisorsIt should be remarked that only Cunningham and Western used a different notation for the expressionpof Fermat's NumbersF, and were in fact originally prepared for, and used for, that purpose._{m}

**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* · 2^{n} + 1, again bound to be “large”
in some way. The precise limitation was set to be
10^{8} < *p* < 10^{12}, 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 · 2^{21} + 1, turned
out to divide the Fermat number *F*_{15}, 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 · 2^{75} + 1, shown by
J. C. Morehead to divide *F*_{73}, in 1905
PDF.

**Robinson 1958.** The paper by Raphael M. Robinson, *A report on primes
of the form k* · 2^{n} + 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 numberA suitable form of the indicated theorem reads:N> 1 can be put in the formN=k· 2^{n}+ l, withkodd,k> 0, andn> 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 ofkinvolved is relatively small. In the course of our computation, all of these numbers withk< 100 andn< 512 were tested for primeness, as well as some numbers lying outside of this range.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 wherenis very small, and here no test is needed.

** Proth's Theorem.** Let

The test is simple, in practice the difficulty is multiplying the large numbers involved.
Incidentally, primes of the considered form satisfying the condition 2^{n} > *k*
of the theorem are now usually called Proth primes.

In Table 1 of Robinson's paper, primes *k* · 2^{n} + 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 · 2^{1947} + 1 which divides the Fermat
number *F*_{1945}. 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* · 2^{n} + 1
PDF.
Table extension to *k* < 130, *n* ≤ 1000 (two Fermat factors).

R. Baillie (1979), *New primes of the form* *k* · 2^{n} + 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* · 2^{n} + 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* · 2^{n} + 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
*F _{m}* = 2

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 *F _{m}*(

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
*F _{m}*(

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
*F _{m}*(

As far as primes *k* · 2^{n} + 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* · 2^{n} + 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 formThe 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 primesk·2^{n}+ 1 that have been tested for primality and he gave me your name.

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.

**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* ·2^{n} + 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* ·2^{n} + 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.