**
Double checking primes of the form
k · 2^{n} + 1 for GFN divisibilities **

**By Gary Gostin**

August 8, 2024

**Introduction and Results Summary**

Primes of the form *k* · 2^{n} + 1 have the potential to divide Fermat numbers
2^{2m} + 1 with *m* ≤ *n* − 2 and Generalized Fermat Numbers (GFNs), both
GF(*m*,*a*) = *a*^{2m} + 1 and xGF(*m*,*a*,*b*) =
*a*^{2m} + *b*^{2m} with *m* ≤ *n* − 1. Primes of this form
with *k* odd, *n* a positive integer and 2^{n} > *k* are referred to as Proth primes. Searching for new large Proth
primes has been the focus of several projects, including organized searches by groups like PrimeGrid and the early ProthSearch, plus individual
efforts. Each new Proth prime discovered is usually reported at PrimePages (https://t5k.org/) if the
prime is in the 5000 largest primes, at PrimeGrid (https://www.primegrid.com/) if discovered
by PrimeGrid, and/or at ProthSearch (http://www.prothsearch.com/) if *k* is small
enough to be included at that site.

New Proth primes are often tested by their discoverer for Fermat and GFN divisibilities (GFNs with *a* ≤ 12 and
*b* < *a*). Divisibilities found can be recorded on PrimePages in the comments for the prime or at PrimeGrid beneath the prime. However,
PrimePages and PrimeGrid do not record if a Proth prime has been tested for Fermat and GFN divisibilities. So, there is no way to distinguish a Proth
prime that was tested for divisibilities, but none were found, from a Proth prime that was not tested.

I discussed this in 2022 with Wilfrid Keller, who maintains the ProthSearch site. He confirmed that there is currently no tracking
on PrimePages, PrimeGrid or elsewhere of which Proth primes have been tested for Fermat and GFN divisibilities. Wilfrid informed me that Proth primes
discovered by PrimeGrid are now automatically tested for divisibilities. But primes from other sources and earlier primes from PrimeGrid may not have
this guarantee of testing for divisibilities. After some discussion, we concluded that some double checking of known primes of the form
*k* · 2^{n} + 1 for Fermat and GFN divisibilities might be worthwhile.

Based on that conclusion, we began a double check project that progressed, intermittently, over the next two years. During the
course of the project, we defined our “double check set” as the set of primes of the form
*k* · 2^{n} + 1 that we would double check for Fermat and GFN divisibilities. That set consists of:

- All primes of this form recorded at PrimePages
- All primes of this form recorded at PrimeGrid
- All primes at ProthSearch in the compact lists at the bottom of the Frequencies page

The goals of this “double check set” definition was a set that is simply defined, timeless, well documented and
includes the primes that would be the most time consuming to test. Note that “timeless” refers to the definition of the set, which allows
for new primes to be added on an ongoing basis. Therefore, this double check set definition also requires an “as-of” date to specify the
exact set of primes tested. Not included in the double check set are primes at PrimePages or PrimeGrid without the term 2^{n} in its
representation but which could be converted into the form *k* · 2^{n} + 1. For example:
9024^{256} + 1 = 141^{256} · 2^{1536} + 1. Also, note that a
*k* · 2^{n} + 1 prime does not have to meet the 2^{n} > *k* Proth requirement
to divide a Fermat number or GFN, so “Proth-ness” was ignored for this project.

Over the course of this project the entire double check set was tested for GFN and Fermat divisibilities. A total of 21 missed GFN divisibilities were discovered, as listed in Results.

The following sections describe the double check project progression and results in greater detail.

**Project Progression**

We began our double check project in July 2022. Initially, we each independently did an experiment to see if any missed
divisibilities could quickly be found. Wilfrid extracted all *k* · 2^{n} + 1 primes with
*k* < 10^{15} from PrimePages on July 14, and then tested those primes with *k* < 10^{5} and *n* ≤ 600000
for divisibilities using pfgw64 (PFGW Version 3.7.10). No missed divisibilities were found. I extracted all
*k* · 2^{n} + 1 primes with *k* < 1000 from PrimePages on July 26, then began testing for
divisibilities starting from the smallest *n* and working upward using a program I wrote based on the gwnum library. The first missed GFN
divisibility was found on 8/17/2022: 935 · 2^{1394813} + 1 divides xGF(1394811,11,4). This prime was found by PrimeGrid on 1/26/2012.
Encouraged by this discovery, I continued the systematic *k* < 1000 double check toward higher *n*, while also testing new Proth primes
reported at PrimePages with very small *k* but without any divisibilities.

In October 2022 Wilfrid and I shared and discussed our double check experiments. By then I had completed *k* < 1000
up to *n* ≤ 2.7M finding no additional missed divisibilities. After our sync-up, Wilfrid pointed out several *k* = 81 Proth primes reported
at PrimePages in the last 3 months that had no divisibilities reported. I tested these, finding 5 missed GFN divisibilities (see
Results). Meanwhile I continued the systematic double check search, completing all
*k* < 1000 primes by the end of November 2022, with the exception of 32 “huge” primes with *n* > 6000000 that already
had reported divisibilities.

Over the next few months, I continued double checking PrimePages primes in higher bands of *k*, finding one additional missed
divisibility. To handle the continuing stream of new Proth primes being reported, I wrote some scripts to extract a list of
*k* · 2^{n} + 1 primes from PrimePages, compare the list to the primes that had already been double
checked, and generate a list of primes remaining to test. By mid-April 2023, all *k* · 2^{n} + 1 primes
from PrimePages with *k* represented as a single integer ≤ 10 digits had been tested (except for the 32 huge primes mentioned above), with no
additional missed divisibilities found. In March 2023 I modified the scripts to extract all *k* · 2^{n} + 1
primes with *k* < 1200 from the riesel1/1a/1b/1c files at ProthSearch and test the
previously untested primes. No missed divisibilities were found.

In early 2023 Wilfrid extracted all *k* · 2^{n} + 1 primes from PrimePages, including
those with *k* having an “exotic” form such as 47# · 2^{90499} + 1. Then, for primes that were
testable by his version of pfgw (which supports a maximum value of *k* of roughly 10^{115}), he tested the following for divisibilities: all
primes with *k* having 8 or more digits, all primes with *k* having 1, 2, 5, 6 or 7 digits and *n* < 1800000, and all primes with
*k* having 3 or 4 digits and *n* < 1000000. All known divisibilities were confirmed and no missed divisibilities were discovered.

For the next several months our discussions moved to other topics, returning to our double check project in November 2023. Wilfrid
had been working on expanding the set of *k* · 2^{n} + 1 primes recorded at ProthSearch to include
compact lists of primes at the bottom of the Frequencies page. These lists were organized as
one set of files for primes with *k* < 1200, which exactly match the primes on the
riesel1/1a/1b/1c pages, plus another set of files for primes with 1200 < *k* < 10000.
Primes in these files are from the early ProthSearch, PrimePages, PrimeGrid and other sources. Wilfrid had double checked all primes with
*n* ≤ 100000 using pfgw and found no missed divisibilities.

In December I started a double check of the ProthSearch primes in the compact files with n > 100000 that I had not previously
tested, plus the 32 huge primes with known divisibilities that I had previously skipped. This double check found 13 missed GFN divisibilities for
13 primes found by PrimeGrid between 2012 and 2013 that were too small to qualify for PrimePages at the time. This double check also found 16
“primes” that are actually composite, all of which were sourced by PrimeGrid. These are listed in
Composite and were removed from ProthSearch. As an additional crosscheck, I modified my scripts
to extract all *k* · 2^{n} + 1 primes directly from PrimeGrid and test the primes not previously tested.
No missed GFN divisibilities were found, but 7 more composite “primes” were discovered. Wilfrid had detected these earlier and not included
them in ProthSearch.

At this point our attention returned to the *k* · 2^{n} + 1 primes at PrimePages
with *k* having an exotic form (not a single integer). Wilfrid had identified some additional primes not included in his early 2023 list. To ensure
our list of primes was complete, we each did some “mining” of PrimePages for primes of exotic forms. Note that primes of the general form
*k* · 2^{n} + 1 are represented at PrimePages in three specific forms:
*k* · 2^{n} + 1, 2^{n} · *k* + 1 and
*k*_{1} · 2^{n} · *k*_{2} + 1.
After comparing and reconciling our extracted lists, we arrived at what we think is a complete list of these primes, shown in
Exotic. Wilfrid tested each of the primes added since his early 2023 double check (where supported
by his pfgw). In addition, I tested all primes in Exotic with the latest version of pfgw64 which
has no limits on *k*. For both of our tests, all primes were confirmed as 3-PRP and no divisibilities were found, as expected, since the
probability of finding a divisibility is O(1/*k*).

In early 2024 I freshly extracted all *k* · 2^{n} + 1 primes from PrimePages,
PrimeGrid and ProthSearch, then tested all primes with *k* being a simple integer ≤ 15 digits (the limit of my gwnum-based program) and not
previously tested. No new divisibilities were found. This double check combined with our double check of primes with smaller *n* and large or
exotic *k* completed the initial double check of all primes of the form *k* · 2^{n} + 1 at
PrimePages, PrimeGrid and ProthSearch.

**Project Results**

All primes in the double check set as of August 2, 2024 have been double checked for GFN and Fermat divisibilities. A total
of 21 missed GFN divisibilities have been discovered, which are listed in Results. The missed
divisibilities are listed in two groups: those that were missed for a short time (2 weeks to 3 months) and those that were missed for a long time
(more than 3 months). Not included in this missed list are divisibilities that were found within two weeks of the prime being reported. These were
considered first time checks, performed primarily on new primes with a small *k* to prevent future missed GFN divisibilities. All missed
divisibilities have been added to ProthSearch and to the user comments at PrimePages, if the prime is included there. While all known divisibilities
for our double check set are recorded at ProthSearch, many previously known divisibilities (mostly with smaller *n*) are missing at PrimePages.
We did not attempt to add these to the user comments due to the huge number of them.

Please note that the last two divisibilities in Results were originally discovered at the time the primes were found in 2022 and 2023 but were not recorded at PrimeGrid due to a “glitch”. See this post for details. These were later added to PrimeGrid in February 2024. Because the original discovery preceded the discovery by our double check effort, these divisibilities have been recorded at ProthSearch as discovered by the PrimeGrid discoverer (Davies).

We considered adding other *k* · 2^{n} + 1 primes to our double check set. However,
the other groups of primes available to us were either not part of an organized search, not documented publicly or not contiguous with the double check
set defined above. Since these characteristics conflicted with the goals of our double check set definition, we decided not to include them in the
project.

Going forward, I will continue to test new primes added to the double check set every few months, plus may do early checks of new
primes reported with small *k* that suspiciously have no reported divisibilities.

We would be very interested to learn about any other Proth prime divisibility double check efforts that others have done. Please send any questions or feedback to the author.

**Related Prime Search Sub-Projects**

During the course of our divisibilities double check project, Wilfrid pointed out that, according to the
Proth Primes: Search and Double-Check Status page, Proth numbers
with 1200 < *k* < 10000 and *n* < 1.422M have not yet been double checked for primality. Since primes in this region provide part
of the “input” for our divisibilities double check project, I decided to spend some time double checking the search for
*k* · 2^{n} + 1 primes with 3 ≤ *k* < 10000, starting at *n* = 5 and working upward.
To date, 5 ≤ *n* ≤ 140000 has been double checked, discovering the 16 missed primes listed in
MissedPrimes. None of these produced new divisibilities.

The compact lists of primes at the ProthSearch Frequencies page
were originally limited to *k* < 10000. During our discussion of whether there were any systematic searches for primes with
*k* > 10000 that might be added to our double check set, Wilfrid pointed out the search conducted by Joe McLean in 2005 for
*k* · 2^{n} + 1 primes with *k* < 100000 and *n* ≤ 10000 (see the bottom of
History). Wilfrid double checked this search in 2017, finding two primes missed by McLean.
To expand on this excellent early work, for 10000 < *k* < 100000 I triple checked the search for primes with *n ≤* 10000,
finding two additional missed primes. I then extended the search up to *n* ≤ 60000, finding 232338 “new” primes and testing
each for GFN and Fermat divisibilities. These primes were included on the Frequencies page.
Note that this region had already been searched for Fermat and GFN divisibilities long ago, and no missed divisibilities were discovered in my
search.