Proth prime
A Proth number is a natural number N of the form N = k × 2 n + 1 {\displaystyle N=k\times 2^{n}+1} where k and n are positive integers, k is odd and 2 n > k {\displaystyle 2^{n}>k} . A Proth prime is a Proth number that is prime. They are named after the French mathematician François Proth. The first few Proth primes are
.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent;color:inherit}.mw-parser-output .infobox-3cols-child{margin:-3px}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}
| Named after |
|---|
| 1878 |
| Proth, Francois |
| 4304683178 below 272 |
| Infinite |
| Proth numbers, prime numbers |
| k × 2n + 1 |
| 3, 5, 13, 17, 41, 97, 113 |
| 10223 × 231172165 + 1 (as of December 2019) |
| .mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}A080076Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m ≥ 1 |
A Proth number is a natural number N of the form
N
=
k
×
2
n
+
1
{\displaystyle N=k\times 2^{n}+1}
where k and n are positive integers, k is odd and
2
n
>
k
{\displaystyle 2^{n}>k}
. A Proth prime is a Proth number that is prime. They are named after the French mathematician François Proth. The first few Proth primes are
3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 (OEIS: A080076).
It is still an open question whether an infinite number of Proth primes exist. It was shown in 2022 that the reciprocal sum of Proth primes converges to a real number near 0.747392479, substantially less than the value of 1.093322456 for the reciprocal sum of Proth numbers.
The primality of Proth numbers can be tested more easily than many other numbers of similar magnitude.
A Proth number takes the form
N
=
k
×
2
n
+
1
{\displaystyle N=k\times 2^{n}+1}
where k and n are positive integers,
k
{\displaystyle k}
is odd and
2
n
>
k
{\displaystyle 2^{n}>k}
. A Proth prime is a Proth number that is prime. Without the condition that
2
n
>
k
{\displaystyle 2^{n}>k}
, all odd integers larger than 1 would be Proth numbers.
.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+span.mw-empty-elt+.hatnote,.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}
The primality of a Proth number can be tested with Proth's theorem, which states that a Proth number
p
{\displaystyle p}
is prime if and only if there exists an integer
a
{\displaystyle a}
for which
a
p
−
1
2
≡
−
1
(
mod
p
)
.
{\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}
This theorem can be used as a probabilistic test of primality, by checking for many random choices of
a
{\displaystyle a}
whether
a
p
−
1
2
≡
−
1
(
mod
p
)
.
{\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}
If this fails to hold for several random
a
{\displaystyle a}
, then it is very likely that the number
p
{\displaystyle p}
is composite. This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".
In 2008, Sze created a deterministic algorithm that runs in at most
O
~
(
(
k
log
k
+
log
N
)
(
log
N
)
2
)
{\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}
time, where Õ is the soft-O notation. For typical searches for Proth primes, usually
k
{\displaystyle k}
is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order
O
(
log
N
)
{\displaystyle O(\log N)}
(e.g. Cullen prime search). In these cases algorithm runs in at most
O
~
(
(
log
N
)
3
)
{\displaystyle {\tilde {O}}((\log N)^{3})}
, or
O
(
(
log
N
)
3
+
ϵ
)
{\displaystyle O((\log N)^{3+\epsilon })}
time for all
ϵ
>
0
{\displaystyle \epsilon >0}
. There is also an algorithm that runs in
O
~
(
(
log
N
)
24
/
7
)
{\displaystyle {\tilde {O}}((\log N)^{24/7})}
time.
Fermat numbers are a special case of Proth numbers, wherein k=1. In such a scenario Pépin's test proves that only base a=3 need to be checked to deterministically verify or falsify the primality of a Fermat number.
As of 2022, the largest known Proth prime is
10223
×
2
31172165
+
1
{\displaystyle 10223\times 2^{31172165}+1}
. It is 9,383,761 digits long. It was found by Szabolcs Peter in the PrimeGrid volunteer computing project which announced it on 6 November 2016. It is also the third largest known non-Mersenne prime.
The project Seventeen or Bust, searching for Proth primes with a certain
t
{\displaystyle t}
to prove that 78557 is the smallest Sierpinski number (Sierpinski problem), has found 11 large Proth primes by 2007. Similar resolutions to the prime Sierpiński problem and extended Sierpiński problem have yielded several more numbers.
Since divisors of Fermat numbers
F
n
=
2
2
n
+
1
{\displaystyle F_{n}=2^{2^{n}}+1}
are always of the form
k
×
2
n
+
2
+
1
{\displaystyle k\times 2^{n+2}+1}
, it is customary to determine if a new Proth prime divides a Fermat number.
As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes. Its main projects include:
-
general Proth prime search
-
321 Prime Search (searching for primes of the form
3 × 2 n + 1{\displaystyle 3\times 2^{n}+1}
, also called Thabit primes of the second kind)
-
27121 Prime Search (searching for primes of the form
27 × 2 n + 1{\displaystyle 27\times 2^{n}+1}
and
121
×
2
n
+
1
{\displaystyle 121\times 2^{n}+1}
)
-
Cullen prime search (searching for primes of the form
n × 2 n + 1{\displaystyle n\times 2^{n}+1}
)
-
Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form
k × 2 n + 1{\displaystyle k\times 2^{n}+1}
where k is in this list:
k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}
As of June 2023, the largest Proth primes discovered are:
| rank | prime | digits | when | Comments | Discoverer (Project) | References |
|---|---|---|---|---|---|---|
| 1 | 10223 × 231172165 + 1 | 9383761 | 31 Oct 2016 | Szabolcs Péter (Sierpinski Problem) | ||
| 2 | 202705 × 221320516 + 1 | 6418121 | 1 Dec 2021 | Pavel Atnashev (Extended Sierpinski Problem) | ||
| 3 | 81 × 220498148 + 1 | 6170560 | 13 Jul 2023 | Generalized Fermat F2(3 × 25124537) | Ryan Propper (LLR) | |
| 4 | 7 × 220267500 + 1 | 6101127 | 21 Jul 2022 | Divides F20267499(12) | Ryan Propper (LLR) | |
| 5 | 168451 × 219375200 + 1 | 5832522 | 17 Sep 2017 | Ben Maloney (Prime Sierpinski Problem) | ||
| 6 | 7 × 218233956 + 1 | 5488969 | 1 Oct 2020 | Divides Fermat F18233954 and F18233952(7) | Ryan Propper | |
| 7 | 13 × 216828072 + 1 | 5065756 | 11 Oct 2023 | Ryan Propper | ||
| 8 | 3 × 216408818 + 1 | 4939547 | 28 Oct 2020 | Divides F16408814(3), F16408817(5), and F16408815(8) | James Brown (PrimeGrid) | |
| 9 | 11 × 215502315 + 1 | 4666663 | 8 Jan 2023 | Divides F15502313(10) | Ryan Propper | |
| 10 | 37 × 215474010 + 1 | 4658143 | 8 Nov 2022 | Ryan Propper | ||
| 11 | (27658613 + 1) × 27658614 + 1 | 4610945 | 31 Jul 2020 | Gaussian Mersenne norm | Ryan Propper and Serge Batalov | |
| 12 | 13 × 215294536 + 1 | 4604116 | 30 Sep 2023 | Ryan Propper | ||
| 13 | 37 × 214166940 + 1 | 4264676 | 24 Jun 2022 | Ryan Propper | ||
| 14 | 99739 × 214019102 + 1 | 4220176 | 24 Dec 2019 | Brian Niegocki (Extended Sierpinski Problem) | ||
| 15 | 404849 × 213764867 + 1 | 4143644 | 10 Mar 2021 | Generalized Cullen with base 131072 | Ryan Propper and Serge Batalov | |
| 16 | 25 × 213719266 + 1 | 4129912 | 21 Sep 2022 | F1(5 × 26859633) | Ryan Propper | |
| 17 | 81 × 213708272 + 1 | 4126603 | 11 Oct 2022 | F2(3 × 23427068) | Ryan Propper | |
| 18 | 81 × 213470584 + 1 | 4055052 | 9 Oct 2022 | F2(3 × 23367646) | Ryan Propper | |
| 19 | 9 × 213334487 + 1 | 4014082 | 31 Mar 2020 | Divides F13334485(3), F13334486(7), and F13334484(8) | Ryan Propper | |
| 20 | 19249 × 213018586 + 1 | 3918990 | 26 Mar 2007 | Konstantin Agafonov (Seventeen or Bust) |
.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}body.skin-vector-2022 .mw-parser-output .reflist-columns-2{column-width:27em}body.skin-vector-2022 .mw-parser-output .reflist-columns-3{column-width:22.5em}.mw-parser-output .references[data-mw-group=upper-alpha]{list-style-type:upper-alpha}.mw-parser-output .references[data-mw-group=upper-roman]{list-style-type:upper-roman}.mw-parser-output .references[data-mw-group=lower-alpha]{list-style-type:lower-alpha}.mw-parser-output .references[data-mw-group=lower-greek]{list-style-type:lower-greek}.mw-parser-output .references[data-mw-group=lower-roman]{list-style-type:lower-roman}.mw-parser-output div.reflist-liststyle-upper-alpha .references{list-style-type:upper-alpha}.mw-parser-output div.reflist-liststyle-upper-roman .references{list-style-type:upper-roman}.mw-parser-output div.reflist-liststyle-lower-alpha .references{list-style-type:lower-alpha}.mw-parser-output div.reflist-liststyle-lower-greek .references{list-style-type:lower-greek}.mw-parser-output div.reflist-liststyle-lower-roman .references{list-style-type:lower-roman}
A Proth number of the second kind is a natural number N of the form
N
=
k
×
2
n
−
1
{\displaystyle N=k\times 2^{n}-1}
where k and n are positive integers, k is odd and
2
n
>
k
{\displaystyle 2^{n}>k}
. A Proth prime of the second kind is a Proth number of the second kind that is prime. The first few Proth primes of the second kind are
3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 (OEIS: A112715).
The largest Proth primes of the second kind can be primality testing use the Lucas–Lehmer–Riesel test.
As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes of the second kind. Its main projects include:
-
general Proth prime of the second kind search
-
321 Prime Search (searching for primes of the form
3 × 2 n − 1{\displaystyle 3\times 2^{n}-1}
, also called Thabit primes)
-
27121 Prime Search (searching for primes of the form
27 × 2 n − 1{\displaystyle 27\times 2^{n}-1}
and
121
×
2
n
−
1
{\displaystyle 121\times 2^{n}-1}
)
-
Woodall prime search (searching for primes of the form
n × 2 n − 1{\displaystyle n\times 2^{n}-1}
)
-
Riesel problem (and their prime and extended generalizations) – searching for primes of the form
k × 2 n − 1{\displaystyle k\times 2^{n}-1}
where k is in this list:
k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743 }
Small Proth primes (less than 10200) have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" (within about 1011) to the previous one. Such ladders have been used to empirically verify prime-related conjectures. For example, Goldbach's weak conjecture was verified in 2008 up to 8.875 × 1030 using prime ladders constructed from Proth primes. (The conjecture was later proved by Harald Helfgott.)
Also, Proth primes can optimize den Boer reduction between the Diffie–Hellman problem and the Discrete logarithm problem. The prime number 55 × 2286 + 1 has been used in this way.
As Proth primes have simple binary representations, they have also been used in fast modular reduction without the need for pre-computation, for example by Microsoft.