Proth number

In number theory, a Proth number is a number of the form

[math]\displaystyle{ N=k \cdot 2^n+1 }[/math]

where [math]\displaystyle{ k }[/math] is an odd positive integer and [math]\displaystyle{ n }[/math] is a positive integer such that [math]\displaystyle{ 2^n \gt k }[/math]. They are named after the mathematician François Proth. The first few Proth numbers are

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241 (sequence A080075 in the OEIS).

The Cullen numbers (numbers of the form $n \cdot2 n + 1$ ) and Fermat numbers (numbers of the form $2 2 n + 1$ ) are special cases of Proth numbers. Without the condition that [math]\displaystyle{ 2^n \gt k }[/math], all odd integers greater than 1 would be Proth numbers.^[1]

Proth primes

Unsolved problem in mathematics:

Are there infinitely many Proth primes?

(more unsolved problems in mathematics)

A Proth prime is a Proth number which is prime. 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).

The primality of a Proth number can be tested with Proth's theorem, which states^[2] that a Proth number [math]\displaystyle{ p }[/math] is prime if and only if there exists an integer [math]\displaystyle{ a }[/math] for which

[math]\displaystyle{ a^{\frac{p-1}{2}}\equiv -1 \pmod{p} . }[/math]

The largest known Proth prime (As of 2016) is [math]\displaystyle{ 10223 \cdot 2^{31172165} + 1 }[/math], and is 9,383,761 digits long.^[3] It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016.^[4] It is also the largest known non-Mersenne prime.^[5]

References

External links

Grime, Dr. James. "78557 and Proth Primes" (video). Brady Haran. https://www.youtube.com/watch?v=fcVjitaM3LY. Retrieved 13 November 2017.

0.00

(0 votes)

[1] Weisstein, Eric W.. "Proth Number". http://mathworld.wolfram.com/ProthNumber.html.

[2] Weisstein, Eric W.. "Proth's Theorem". http://mathworld.wolfram.com/ProthsTheorem.html.

[3] Caldwell, Chris. "The Top Twenty: Proth". The Prime Pages. http://primes.utm.edu/top20/page.php?id=66.

[4] Van Zimmerman (30 Nov 2016). "World Record Colbert Number discovered!". PrimeGrid. http://www.primegrid.com/forum_thread.php?id=7116.

[5] Caldwell, Chris. "The Top Twenty: Largest Known Primes". The Prime Pages. http://primes.utm.edu/top20/page.php?id=3.

[1]

[2]

[3]

[4]

[5]

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Carol $(2 n - 1) 2 - 2$ Kynea $(2 n + 1) 2 - 2$ Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient
Base-dependent	Happy Dihedral Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k−Tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Safe ( $p, (p - 1)/2$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Titanic (1,000+ digits) Gigantic (10,000+ digits) Mega (1,000,000+ digits) Largest known
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Somer–Lucas Strong Carmichael number Almost prime Semiprime Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers

Anonymous

Search

Proth number

Namespaces

More

Page actions

Contents

Proth primes

See also

References

External links

Navigation

Navigation

Help

Translate

Wiki tools

Wiki tools

Anonymous

Search

Proth number

Proth primes

See also

References

External links

Navigation

Wiki tools

Page tools

Other projects

Categories