A Proth number is a

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

''N'' of the form

N = k \times 2^n +1

where ''k'' and ''n'' are positive

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

s, ''k'' is

odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...

and

2^n > k

. A Proth prime is a Proth number that is

prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

. They are named after the French mathematician

François Proth François Proth (22 March 1852 – 21 January 1879) was a French self-taught mathematician farmer who lived in Vaux-devant-Damloup near Verdun, France. He stated four primality-related theorems. The most famous of these, Proth's theorem, can ...

. 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 (). 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.

Definition

A Proth number takes the form

N=k 2^n +1

where ''k'' and ''n'' are positive integers,

k

is odd and

2^n>k

. A Proth prime is a Proth number that is prime. Without the condition that

2^n > k

, all odd integers larger than 1 would be Proth numbers.

Primality testing

The primality of a Proth number can be tested with

Proth's theorem In number theory, Proth's theorem is a primality test for Proth numbers. It states that if ''p'' is a Proth number, of the form ''k''2''n'' + 1 with ''k'' odd and ''k'' < 2^''n'', and if there exists an

, which states that a Proth number

p

is prime if and only if there exists an integer

a

for which :

a^\equiv -1 \pmod.

This theorem can be used as a probabilistic test of primality, by checking for many random choices of

a

whether

a^\equiv -1 \pmod.

If this fails to hold for several random

a

, then it is very likely that the number

p

composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic materials ...

. This test is a

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...

: it never returns a

false positive A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test result ...

but can return a

false negative A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test result ...

; 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 In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...

that runs in at most

\tilde((k\log k+\log N)(\log N)^2)

time, where Õ is the soft-O notation. For typical searches for Proth primes, usually

k

is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order

O(\log N)

(e.g.

Cullen prime Cullen may refer to: Places Canada *Cullen, Saskatchewan, a former hamlet in Benson No. 35 Rural Municipality Ireland *Cullen, County Cork, a village near Boherbue, County Cork *Cullen, County Tipperary, a small village in County Tipperary Scotl ...

search). In these cases algorithm runs in at most

\tilde((\log N)^3)

, or

O((\log N)^)

time for all

\epsilon>0

. There is also an algorithm that runs in

\tilde((\log N)^)

time.

Large primes

, the largest known Proth prime is

10223 \times 2^ + 1

. It is 9,383,761 digits long. It was found by Szabolcs Peter in the

PrimeGrid PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ...

volunteer computing project which announced it on 6 November 2016. It is also the largest known non-

Mersenne prime In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...

. The project

Seventeen or Bust Seventeen or Bust was a volunteer computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem. The project solved eleven cases before a server loss in April 2016 forced it to cease operations. Work on the ...

, searching for Proth primes with a certain

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 number In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form :F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers are: : 3, 5, 17, 257, 65537, 4294967 ...

F_n = 2^ + 1

are always of the form

k \times 2^ + 1

, it is customary to determine if a new Proth prime divides a Fermat number. As of June 2022,

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\times2^n+1

, also called Thabit primes of the second kind) * 27121 Prime Search (searching for primes of the form

27\times2^n+1

and

121\times2^n+1

) * Cullen prime search (searching for primes of the form

n\times2^n+1

) *Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form

k \times 2^n+1

where ''k'' is in this list:

''k'' ∈

As of December 2022, the largest Proth primes discovered are:

Uses

Small Proth primes (less than 10²⁰⁰) have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" (within about 10¹¹) to the previous one. Such ladders have been used to empirically verify prime-related

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

s. For example,

Goldbach's weak conjecture In number theory, Goldbach's weak conjecture, also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem, states that : Every odd number greater than 5 can be expressed as the sum of three primes. (A prime ma ...

was verified in 2008 up to 8.875 × 10³⁰ using prime ladders constructed from Proth primes. (The conjecture was later proved by

Harald Helfgott Harald Andrés Helfgott (born 25 November 1977) is a Peruvian mathematician working in number theory. Helfgott is a researcher ('' directeur de recherche'') at the CNRS at the Institut Mathématique de Jussieu, Paris. Early life and education ...

.) Also, Proth primes can optimize

den Boer reduction Den may refer to: * Den (room), a small room in a house * Maternity den, a lair where an animal gives birth Media and entertainment * ''Den'' (album), 2012, by Kreidler * Den (''Battle Angel Alita''), a character in the ''Battle Angel Alita' ...

between the Diffie-Hellman problem and the

Discrete logarithm problem In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b'' ...

. The prime number 55 × 2²⁸⁶ + 1 has been used in this way. As Proth primes have simple

binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...

representations, they have also been used in fast modular reduction without the need for pre-computation, for example by

Microsoft Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...

References

{{Prime number classes Classes of prime numbers