Wagstaff prime number

In number theory , a Wagstaff prime is a prime number of the form ${\displaystyle p}$

${\displaystyle p={\frac {2^{q}+1}{3}}}$ with an odd prime number ${\displaystyle q\in \mathbb {P} }$

These numbers were named after the mathematician Samuel Wagstaff and appear among other things in the new Mersenne conjecture .

Examples

• The first Wagstaff primes are the following:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243, 62357403192785191176690552862561408838653121833643 ... (sequence A000979 in OEIS )

The following applies to the first three of these prime numbers:

${\displaystyle 3={\frac {2^{3}+1}{3}}}$, , , ... ${\displaystyle 11={\frac {2^{5}+1}{3}}}$ ${\displaystyle 43={\frac {2^{7}+1}{3}}}$

• The first exponents that lead to Wagstaff primes are the following: ${\displaystyle q\in \mathbb {P} }$ ${\displaystyle p={\frac {2^{q}+1}{3}}}$

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339 (sequence A000978 in OEIS )

• The other exponents that lead to possible Wagstaff prime numbers are the following (at the moment they are not yet proven prime numbers, i.e. probable primes , PRP ): ${\displaystyle q\in \mathbb {P} }$

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399,…, 13347311, 13372531 (sequence A000978 in OEIS )

• In February 2010 Tony Reix discovered the number that has all the requirements to be a Wagstaff prime number. It is a so-called probable prime (PRP) . She has jobs and at the time it was the third largest PRP number ever found. To this day, it is still not known whether it is really a true prime or just a pseudo- prime number . ${\displaystyle {\frac {2^{4031399}+1}{3}}}$ ${\displaystyle 1213572}$
• In September 2013 Ryan Propper discovered the two largest potential Wagstaff prime numbers to date (as of June 16, 2018), namely the two numbers with digits and the number with digits. Both numbers are currently the largest probable primes (PRP) that have been discovered to date. ${\displaystyle {\frac {2^{13347311}+1}{3}}}$ ${\displaystyle 4017941}$ ${\displaystyle {\frac {2^{13372531}+1}{3}}}$ ${\displaystyle 4025533}$

properties

• Let be a Wagstaff prime. Then: ${\displaystyle p\in \mathbb {P} }$

${\displaystyle {\frac {2^{p}+1}{3}}}$ doesn't necessarily have to be a prime number

Proof: The smallest counterexample is: is not a prime number. ${\displaystyle {\frac {2^{683}+1}{3}}=1676083\cdot 26955961001\cdot Z_{189}}$

Unsolved problems

• The following statement is assumed :

Let be a Wagstaff prime with . Then: ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle p>43}$

${\displaystyle {\frac {2^{p}+1}{3}}}$ is always composed.

• Are the Wagstaff numbers already mentioned above with the following exponents actually Wagstaff prime numbers, or are they just pseudo prime numbers (so-called PRP numbers ): ${\displaystyle {\frac {2^{p}+1}{3}}}$ ${\displaystyle p}$

95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399,…, 13347311, 13372531 (sequence A000978 in OEIS )

useful information

It is extremely difficult to prove that Wagstaff numbers are actually prime numbers. This explains the many PRP numbers that have not yet been clearly identified as prime numbers. They satisfy many properties of prime numbers, but they could also be pseudoprimes. At the moment the fastest algorithm with which one can recognize Wagstaff numbers as prime numbers is the program ECPP , which requires elliptic curves for this (hence the name of the program: Elliptic Curve Primality Proving - ECPP ). The largest secured Wagstaff prime number with digits to date is one of the 10 largest prime numbers that have been found with this method so far. The program LLR ( Lucas-Lehmer-Riesel test ( s )) by Jean Penne potential Wagstaff prime candidates are found. ${\displaystyle {\frac {2^{83339}+1}{3}}}$ ${\displaystyle 25088}$

generalization

A Wagstaff number with base b has the form

${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$with a base , and an odd number ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle b\geq 2}$ ${\displaystyle n\in \mathbb {N} }$

A prime Wagstaff number with a base is called a Wagstaff prime number with a base b . ${\displaystyle b}$

Examples

• The following is a table from which the smallest exponents can be found, so that one contains either a Wagstaff prime number with a base or at least a very probable Wagstaff prime number with a base (i.e. a PRP number ): ${\displaystyle n\in \mathbb {P} }$ ${\displaystyle b}$ ${\displaystyle b}$

${\displaystyle b}$	shape	Potencies so Wagstaff primes with base , so the shape , prim or PRP are ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle {\frac {b^{n}+1}{b+1}}}$	OEIS episode
${\displaystyle 2}$	${\displaystyle {\frac {2^{n}+1}{3}}}$	3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ... (the original Wagstaff prime numbers)	(Follow A000978 in OEIS )
${\displaystyle 3}$	${\displaystyle {\frac {3^{n}+1}{4}}}$	3, 5, 7, 13, 23, 43, 281, 359, 487, 577, 1579, 1663, 1741, 3191, 9209, 11257, 12743, 13093, 17027, 26633, 104243, 134227, 152287, 700897, 1205459, 1896463, 2533963, ...	(Follow A007658 in OEIS )
${\displaystyle 4}$	${\displaystyle {\frac {4^{n}+1}{5}}}$	3 (there are no further Wagstaff primes with a base because ) ${\displaystyle b=4}$ ${\displaystyle 4^{n}+1=(2^{n}-2^{\frac {n+1}{2}}+1)\cdot (2^{n}+2^{\frac {n+1}{2}}+1)}$
${\displaystyle 5}$	${\displaystyle {\frac {5^{n}+1}{6}}}$	5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, 1856147, ...	(Follow A057171 in OEIS )
${\displaystyle 6}$	${\displaystyle {\frac {6^{n}+1}{7}}}$	3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, 1313371, ...	(Follow A057172 in OEIS )
${\displaystyle 7}$	${\displaystyle {\frac {7^{n}+1}{8}}}$	3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, 1178033, ...	(Follow A057173 in OEIS )
${\displaystyle 8}$	${\displaystyle {\frac {8^{n}+1}{9}}}$	(there are no Wagstaff primes with a base ) ${\displaystyle b=8}$
${\displaystyle 9}$	${\displaystyle {\frac {9^{n}+1}{10}}}$	3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, 703393, ...	(Follow A057175 in OEIS )
${\displaystyle 10}$	${\displaystyle {\frac {10^{n}+1}{11}}}$	5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, 1600787, ...	(Follow A001562 in OEIS )
${\displaystyle 11}$	${\displaystyle {\frac {11^{n}+1}{12}}}$	5, 7, 179, 229, 439, 557, 6113, 223999, 327001, ...	(Follow A057177 in OEIS )
${\displaystyle 12}$	${\displaystyle {\frac {12^{n}+1}{13}}}$	5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, 495953, ...	(Follow A057178 in OEIS )
${\displaystyle 13}$	${\displaystyle {\frac {13^{n}+1}{14}}}$	3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, 1199467, ...	(Follow A057179 in OEIS )
${\displaystyle 14}$	${\displaystyle {\frac {14^{n}+1}{15}}}$	7, 53, 503, 1229, 22637, 1091401, ...	(Follow A057180 in OEIS )
${\displaystyle 15}$	${\displaystyle {\frac {15^{n}+1}{16}}}$	3, 7, 29, 1091, 2423, 54449, 67489, 551927, ...	(Follow A057181 in OEIS )
${\displaystyle 16}$	${\displaystyle {\frac {16^{n}+1}{17}}}$	3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, ...	(Follow A057182 in OEIS )
${\displaystyle 17}$	${\displaystyle {\frac {17^{n}+1}{18}}}$	7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, ...	(Follow A057183 in OEIS )
${\displaystyle 18}$	${\displaystyle {\frac {18^{n}+1}{19}}}$	3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, ...	(Follow A057184 in OEIS )
${\displaystyle 19}$	${\displaystyle {\frac {19^{n}+1}{20}}}$	17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, 476929, ...	(Follow A057185 in OEIS )
${\displaystyle 20}$	${\displaystyle {\frac {20^{n}+1}{21}}}$	5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, 393257, ...	(Follow A057186 in OEIS )
${\displaystyle 21}$	${\displaystyle {\frac {21^{n}+1}{22}}}$	3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, 394579, ...	(Follow A057187 in OEIS )
${\displaystyle 22}$	${\displaystyle {\frac {22^{n}+1}{23}}}$	3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, ...	(Follow A057188 in OEIS )
${\displaystyle 23}$	${\displaystyle {\frac {23^{n}+1}{24}}}$	11, 13, 67, 109, 331, 587, 24071, 29881, 44053, ...	(Follow A057189 in OEIS )
${\displaystyle 24}$	${\displaystyle {\frac {24^{n}+1}{25}}}$	7, 11, 19, 2207, 2477, 4951, ...	(Follow A057190 in OEIS )
${\displaystyle 25}$	${\displaystyle {\frac {25^{n}+1}{26}}}$	3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, ...	(Follow A057191 in OEIS )

• Further Wagstaff prime numbers with a basis for can be found. ${\displaystyle b}$ ${\displaystyle 25<b\leq 200}$
• The smallest Wagstaff primes with a base (i.e. the form ) are the following: ${\displaystyle b=10}$ ${\displaystyle {\frac {10^{n}+1}{11}}}$

9091, 909091, 909090909090909091, 909090909090909090909090909091, ... (Follow A097209 in OEIS )

The corresponding can be found in the table above. ${\displaystyle n}$

• The smallest prime numbers so that is prime are the following (for ; if there is no such prime number , 0 stands ): ${\displaystyle p\in \mathbb {P} }$ ${\displaystyle Q(b,p)={\frac {b^{p}+1}{b+1}}}$ ${\displaystyle b=2,3,4,\ldots }$ ${\displaystyle p}$

3, 3, 3, 5, 3, 3, 0 , 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0 , 3, 7, 139, 109, 0 , 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0 , 19, 7, 3, 757, 11, 3, 5, 3, ... (sequence A084742 in OEIS )

Example 1: In the 25th position of the above list (i.e. for ) there is a . ${\displaystyle b=26}$ ${\displaystyle 11}$

Thus the smallest Wagstaff prime is with a base . ${\displaystyle Q(26,11)={\frac {26^{11}+1}{26+1}}=135938684703251\in \mathbb {P} }$ ${\displaystyle b=26}$

Example 2: In the 26th position of the list above (i.e. for ) there is a . ${\displaystyle b=27}$ ${\displaystyle 0}$

So there are no Wagstaff primes with a base (so is always ) ${\displaystyle b=27}$ ${\displaystyle Q(27,n)={\frac {27^{n}+1}{27+1}}\not \in \mathbb {P} }$

• Let the -th prime number. The smallest bases such that is prime are the following (for ): ${\displaystyle Prim(n)}$ ${\displaystyle n}$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle Q(b,Prim(n))={\frac {b^{Prim(n)}+1}{b+1}}}$ ${\displaystyle n=2,3,4,\ldots }$

2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, 159, ... (follow A103795 in OEIS )

Example 1: In the 11th position of the above list (i.e. for ) there is a . The 12th prime number is 37 so it is . ${\displaystyle n=12}$ ${\displaystyle 16}$ ${\displaystyle Prim(n)=Prim(12)=37}$

Thus the Wagstaff prime number has the smallest base , where the exponent must be. ${\displaystyle Q(16,37)={\frac {16^{37}+1}{16+1}}\in \mathbb {P} }$ ${\displaystyle b=16}$ ${\displaystyle 37}$

Example 2: In the 24th position of the above list (i.e. for ) there is a . The 25th prime number is 97, so it is . ${\displaystyle n=25}$ ${\displaystyle 70}$ ${\displaystyle Prim(n)=Prim(25)=97}$

Thus the Wagstaff prime number has the smallest base , where the exponent must be. ${\displaystyle Q(70,97)={\frac {70^{97}+1}{70+1}}\in \mathbb {P} }$ ${\displaystyle b=70}$ ${\displaystyle 97}$

properties

• For a Wagstaff prime number with a base (i.e. the form ) the following must always apply: ${\displaystyle b}$ ${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$

${\displaystyle n\in \mathbb {P} }$ is an odd prime number

The converse does not apply: if is an odd prime number, the corresponding Wagstaff number with a base need not be prime. ${\displaystyle n\in \mathbb {P} }$ ${\displaystyle b}$

• Let be a Wagstaff number with a base with , odd ( i.e. (sequence A070265 in OEIS )). ${\displaystyle Q(b,n)={\frac {b^{n}+1}{b+1}}}$ ${\displaystyle b}$ ${\displaystyle b=a^{m}}$ ${\displaystyle m>1}$ ${\displaystyle b\in \{1,8,27,32,64,125,128,\ldots \}}$

Then:

The base Wagstaff number is never prime ${\displaystyle b}$ ${\displaystyle Q(a^{m},n)={\frac {(a^{m})^{n}+1}{a^{m}+1}}}$

In the table above you can see that there are no Wagstaff primes with a base . ${\displaystyle b=8}$ ${\displaystyle b=8}$

Individual evidence

1. ^ PT Bateman, JL Selfridge, SS Wagstaff Jr .: The New Mersenne Conjecture. The American Mathematical Monthly 96 , 1989, pp. 125–128 , accessed June 16, 2018 . 
2. ↑ Chris K. Caldwell: The Top Twenty: Wagstaff. Prime Pages, accessed June 16, 2018 . 
3. ^ ^{A b} Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000. PRP Records, accessed June 16, 2018 . 
4. ↑ Chris K. Caldwell: The Top Twenty: Elliptic Curve Primality Proof. Prime Pages, accessed June 16, 2018 . 
5. ↑ Download Jean Penné's LLR
6. ↑ ^{a b c} Harvey Dubner: Primes of the Form (b ⁿ + 1) / (b + 1). Journal of Integer Sequences 3 , 2000, pp. 1-9 , accessed June 16, 2018 . 
7. ^ Henri Lifchitz: Mersenne and Fermat primes field. Retrieved June 17, 2018 . 
8. ↑ Richard Fischer: General Repunitpaar primes (B ^ N + 1) / (B + 1). Retrieved June 17, 2018 . 

Web links

• Chris K. Caldwell: Wagstaff Prime. The Prime Glossary, accessed June 13, 2018 . 
• Renaud Lifchitz, Henri Lifchitz: An efficient probable prime test for numbers of the form (2 ⁿ  + 1) / 3. Retrieved June 17, 2018 . 
• Tony Reix: Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x ²  - 2 modulo a prime. Retrieved June 17, 2018 . 
• Wagstaff Prime . In: PlanetMath . (English)
• Eric W. Weisstein : Wagstaff Prime . In: MathWorld (English).
• Eric W. Weisstein : New Mersenne Prime Conjecture . In: MathWorld (English).

swell

• PT Bateman, JL Selfridge, SS Wagstaff Jr .: The New Mersenne Conjecture . In: The American Mathematical Monthly . tape 109 , 1989, pp. 125-128 .