A possible source of interesting primes

 Study.com source

Pierre de Fermat was fluent in six languages. Yes I thought we would talk about Fermat today. Something I did not know about him is: he was fluent in French, Latin, Greek, Italian, Spanish, and Occitan. I am impressed since I never could handle another language, though Ken speaks several. Occitan is a relative of Catalan and some of its constituent dialects may be more-familiar names: Langue d’Oc, Provençal, Gascon, and Limousin.

Today Ken and I thought we would discuss something named for Fermat: Fermat primes. A Fermat prime is any prime of the form ${2^n + 1}$.

A Fermat prime is any prime of the form

$\displaystyle 2^{2^n} + 1.$

No, we did not contradict or repeat ourselves. Understanding why ${2^n + 1}$ can possibly be prime only when ${n}$ is a power of ${2}$ is the beginning of learning the language of number theory. Any other ${n > 1}$ includes an odd prime factor ${s > 1}$. Put ${r = n/s}$. Then ${2^n + 1 = x^s - y^s}$ where ${x = 2^r}$ and ${y = -1}$; note that ${y}$ uses ${s}$ being odd. The basic fact is that ${x^s - y^s}$ is always divisible by ${x - y}$ (which in this case equals ${2^r + 1}$), so ${2^n + 1}$ is not prime.

Fermat primes are quite useful, but unfortunately there seem to only be five of them:

$\displaystyle 3,5,17,257,65537.$

There are applications of Fermat primes that could really use having an infinite family of them. A prime case—bad pun—is the beautiful work of Martin Fürer on fast multiplication of integers.

Generalized Fermat Primes

This has led us to seek larger families that might have similar applications. There are of course generalized Fermat primes, which are defined as primes of the form

$\displaystyle b^{2^{k}} + 1$

for any base ${b}$. Obviously for ${b=2}$ they are the Fermat primes.

These numbers seem to be in relative abundance. Indeed, currently the 13th largest known prime is the generalized Fermat number with ${b = 919,\!444}$ and ${k = 20}$.

Whether there are infinitely many generalized Fermat primes is trivial for ${k = 0}$ but already for ${k = 1}$ it subsumes the fourth problem listed by Edmund Landau in his address to the International Congress of Mathematicians in 1912, twelve years after David Hilbert gave his famous list. The problem of whether infinitely many primes are one more than a square traces back at least to Leonhard Euler.

We are, however, interested in special primes amid lists of single-exponential rather than double-exponential density. Marin Mersenne studied primes of the form ${2^n - 1}$ several decades before Fermat. Eleven of the twelve largest known primes have this form, but again no one knows whether there are infinitely many. So we consider other odd numbers near ${2^n}$.

Almost Fermat Primes

Close to Fermat primes are primes among the numbers of the form:

$\displaystyle 2^{n} + 3.$

A simple implementation of a probabilistic primality test, such as this in Python by Eli Bendersky, suffices to find them up to ${n = 10,\!000}$ or so. The simplicity owes to Python’s arbitrary-precision integer arithmetic. After ${n = 1,2,3,4,6,7,12,15,16,18,28,30,55,67,84}$ the list has gaps but also mini-clusters:

prime at ${2^{228} + 3}$
prime at ${2^{390} + 3}$
prime at ${2^{784} + 3}$
prime at ${2^{1110} + 3}$
prime at ${2^{1704} + 3}$
prime at ${2^{2008} + 3}$
prime at ${2^{2139} + 3}$
prime at ${2^{2191} + 3}$
prime at ${2^{2367} + 3}$
prime at ${2^{2370} + 3}$
prime at ${2^{4002} + 3}$
prime at ${2^{4060} + 3}$
prime at ${2^{4062} + 3}$
prime at ${2^{4552} + 3}$
prime at ${2^{5547} + 3}$
prime at ${2^{8739} + 3}$

This gives an impression of greater abundance. The whole known sequence of such ${n}$ is A057732 at the Online Encyclopedia of Integer Sequences.

Bounded Almost Fermat (and Mersenne)

The sequence A059242 of ${n}$ such that ${2^n + 5}$ is prime starts out ${n = 1, 3, 5, 11, 47, 53, 141, 143, 191, 273, 341}$. Then there is a big jump to ${n = 16541, 34001, 34763, 42167, 193965, 282203}$.

There are some ${k}$ such that ${2^n + k}$ is always composite. An entertaining talk by Carl Pomerance ascribed ${k = 9262111}$ to Paul Erdős but this needed to be fixed to ${k = 1518781}$. But we are interested concretely in small ${k}$.

Our desire may ultimately be to have a fixed ${K}$ that gives a sequence of primes ${2^n + k}$ for ${k \leq K}$ that is not only infinite but has linear density in ${n}$. That is, we want some fixed ${r}$ as well as ${K}$ such that for any prime ${p = 2^n + k}$ in our sequence, there is ${n' \leq r n}$ and ${k' \leq K}$ such that ${p' = 2^{n'} + k'}$ is prime. This ensures

$\displaystyle p' \leq 2^{rn} + k' < (2^n + k)^r = p^r$

(ignoring possible low-order exceptions to the second inequality), so that the next item in our sequence is polynomially bounded. Thinking of the ${m}$-th element of our sequence as ${P_m}$, we would get a rough bound

$\displaystyle P_r \approx 2^{r^m},$

so that the density becomes analogous to that of Fermat numbers. We might allow ${K}$ to be slowly growing in ${n}$, e.g., ${K = \log\log n}$.

Here we are thinking of ${p}$ and ${p'}$ as “magic primes” that may allow certain algorithmic ideas to succeed. The density condition ensures the existence of some ${p}$ of magnitude polynomial in the complexity parameter(s). If we only need that the length of ${p}$ is polynomial then we might tolerate a weaker density condition such as ${n' \leq n^r}$ in the above.

Among values of ${k > 3}$ we prioritize those of the form ${2^j + 1}$ so that the binary expansion of ${2^n + k}$ has only three 1’s. Hence also we are less interested in the extension of Mersenne primes to negative ${k \geq -K}$. Here is a table with ${1 \leq k \leq 33 = 2^5 + 1}$ and ${1000 \leq n < 10000}$:

The clusters of 3 seem to stand out the most. As noted above, there are no ${k = 5}$ cases in this range. Of course, this is a small slice of data.

Open Problems

Are there ways to exploit the fact that there appear to be many almost-Fermat numbers? Of course proving there are an infinite number of them could be very hard.