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.
Definition 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.
Primality testing
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.
… excerpt ends here. Continue reading the full article.
