Double checking primes of the form
k · 2n + 1 for GFN divisibilities
By Gary Gostin
August 8, 2024
Introduction and Results Summary
Primes of the form k · 2n + 1 have the potential to divide Fermat numbers 22m + 1 with m ≤ n − 2 and Generalized Fermat Numbers (GFNs), both GF(m,a) = a2m + 1 and xGF(m,a,b) = a2m + b2m with m ≤ n − 1. Primes of this form with k odd, n a positive integer and 2n > 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 · 2n + 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 · 2n + 1 that we would double check for Fermat and GFN divisibilities. That set consists of:
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 2n in its representation but which could be converted into the form k · 2n + 1. For example: 9024256 + 1 = 141256 · 21536 + 1. Also, note that a k · 2n + 1 prime does not have to meet the 2n > 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 · 2n + 1 primes with k < 1015 from PrimePages on July 14, and then tested those primes with k < 105 and n ≤ 600000 for divisibilities using pfgw64 (PFGW Version 3.7.10). No missed divisibilities were found. I extracted all k · 2n + 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 · 21394813 + 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 · 2n + 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 · 2n + 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 · 2n + 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 · 2n + 1 primes from PrimePages, including those with k having an “exotic” form such as 47# · 290499 + 1. Then, for primes that were testable by his version of pfgw (which supports a maximum value of k of roughly 10115), 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 · 2n + 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 · 2n + 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 · 2n + 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 · 2n + 1 are represented at PrimePages in three specific forms: k · 2n + 1, 2n · k + 1 and k1 · 2n · k2 + 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 · 2n + 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 · 2n + 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 · 2n + 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 · 2n + 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 · 2n + 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.