/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
Proth primes
A Proth number is an integer $N = k \cdot 2^n + 1$ where $k$ is odd and $1 \le k < 2^n$. A Proth
number that is prime is called a Proth prime. Proth proved in 1878 that a Proth number $N$ is
prime if and only if $-1$ is an $((N - 1)/2)$-th power modulo $N$. It remains open whether
infinitely many Proth primes exist, and in particular whether any fixed odd multiplier such as
$k = 3$ produces infinitely many primes $3 \cdot 2^n + 1$.
There are infinitely many integers $n \ge 2$ such that $3 \cdot 2^n + 1$ is a Proth prime.
Primes of the form $3 \cdot 2^n + 1$ are also called Thabit primes of the second kind
(Wikipedia: Thabit number). Their exponents are
listed in OEIS A002253, which also includes $n = 1$ ($3 \cdot 2^1 + 1 =
7$ is prime, whereas $n \ge 2$ ensures $3 < 2^n$).