Wagstaff prime

Wagstaff prime
Named after	Samuel S. Wagstaff, Jr.
Publication year	1989
Author of publication	Bateman, P. T., Selfridge, J. L., Wagstaff Jr., S. S.
No. of known terms	44
First terms	3, 11, 43, 683
Largest known term	(2138937+1)/3
OEIS index	A000979 ; Wagstaff primes: primes of form (2^p + 1)/3;

Last updated September 13, 2024

In number theory, a Wagstaff prime is a prime number of the form

Examples

The first three Wagstaff primes are 3, 11, and 43 because

{\begin{aligned}3&={2^{3}+1 \over 3},\\[5pt]11&={2^{5}+1 \over 3},\\[5pt]43&={2^{7}+1 \over 3}.\end{aligned}}

Known Wagstaff primes

The first few Wagstaff primes are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... (sequence A000979 in the OEIS )

Exponents which produce Wagstaff primes or probable primes are:

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, ... (sequence A000978 in the OEIS )

Generalizations

It is natural to consider^[2] more generally numbers of the form

Q(b,n)={\frac {b^{n}+1}{b+1}}

where the base $b\geq 2$ . Since for $n$ odd we have

{\frac {b^{n}+1}{b+1}}={\frac {(-b)^{n}-1}{(-b)-1}}=R_{n}(-b)

these numbers are called "Wagstaff numbers base $b$ ", and sometimes considered^[3] a case of the repunit numbers with negative base $-b$ .

For some specific values of $b$ , all $Q(b,n)$ (with a possible exception for very small $n$ ) are composite because of an "algebraic" factorization. Specifically, if $b$ has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. (sequence A070265 in the OEIS )), then the fact that $x^{m}+1$ , with $m$ odd, is divisible by $x+1$ shows that $Q(a^{m},n)$ is divisible by $a^{n}+1$ in these special cases. Another case is $b=4k^{4}$ , with k a positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. (sequence A141046 in the OEIS )), where we have the aurifeuillean factorization.

However, when $b$ does not admit an algebraic factorization, it is conjectured that an infinite number of $n$ values make $Q(b,n)$ prime, notice all $n$ are odd primes.

For $b=10$ , the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … (sequence A097209 in the OEIS ), and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... (sequence A001562 in the OEIS ).

See Repunit#Repunit primes for the list of the generalized Wagstaff primes base $b$ . (Generalized Wagstaff primes base $b$ are generalized repunit primes base $-b$ with odd $n$ )

The least primes p such that $Q(n,p)$ is prime are (starts with n = 2, 0 if no such p exists)

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 the OEIS )

The least bases b such that $Q(b,prime(n))$ is prime are (starts with n = 2)

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, ... (sequence A103795 in the OEIS )

Related Research Articles

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 $M n = 2 n - 1$ for some integer $n$ . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If $n$ is a composite number then so is $2 n - 1$ . Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form $M p = 2 p - 1$ for some prime $p$ .

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number 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 of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form: $where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....$

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for "repeated unit" and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

In recreational mathematics, a repdigit or sometimes monodigit is a natural number composed of repeated instances of the same digit in a positional number system. The word is a portmanteau of "repeated" and "digit". Examples are 11, 666, 4444, and 999999. All repdigits are palindromic numbers and are multiples of repunits. Other well-known repdigits include the repunit primes and in particular the Mersenne primes.

In number theory, a Wieferich prime is a prime number p such that p² divides $2 p - 1 - 1$ , therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides $2 p - 1 - 1$ . Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.

In number theory, a regular prime is a special kind of prime number, defined by Ernst Kummer in 1850 to prove certain cases of Fermat's Last Theorem. Regular primes may be defined via the divisibility of either class numbers or of Bernoulli numbers.

23 (twenty-three) is the natural number following 22 and preceding 24.

127 is the natural number following 126 and preceding 128. It is also a prime number.

In mathematics, a double Mersenne number is a Mersenne number of the form

In number theory, a practical number or panarithmic number is a positive integer $such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.$

271 is the natural number after 270 and before 272.

In mathematics, the Mersenne conjectures concern the characterization of a kind of prime numbers called Mersenne primes, meaning prime numbers that are a power of two minus one.

In mathematics, specifically in number theory, a Cunningham number is a certain kind of integer named after English mathematician A. J. C. Cunningham.

References

↑ Bateman, P. T.; Selfridge, J. L.; Wagstaff, Jr., S. S. (1989). "The New Mersenne Conjecture". American Mathematical Monthly. 96: 125–128. doi:10.2307/2323195. JSTOR 2323195.
↑ Dubner, H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)
↑ Repunit, Wolfram MathWorld (Eric W. Weisstein)

External links

John Renze and Eric W. Weisstein. "Wagstaff prime". MathWorld .
Chris Caldwell, The Top Twenty: Wagstaff at The Prime Pages.
Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2^p + 1)/3".
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".
List of repunits in base -50 to 50
List of Wagstaff primes base 2 to 160

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Bateman, P. T.; Selfridge, J. L.; Wagstaff, Jr., S. S. (1989). "The New Mersenne Conjecture". American Mathematical Monthly. 96: 125–128. doi:10.2307/2323195. JSTOR 2323195.

[2] Dubner, H. and Granlund, T.: Primes of the Form (bⁿ + 1)/(b + 1), Journal of Integer Sequences, Vol. 3 (2000)

[3] Repunit, Wolfram MathWorld (Eric W. Weisstein)

[1]

[2]

[3]

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$ ) 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
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 Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 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/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number 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