Wagstaff prime

The first three Wagstaff primes are 3, 11, and 43 because :\begin{align} 3 & = {2^3+1 \over 3}, \\[5pt] 11 & = {2^5+1 \over 3}, \\[5pt] 43 & = {2^7+1 \over 3}. \end{align} Wagstaff-Lifchitz primality test :\frac{2^p+1}{3} \text{ is prime} \Longleftrightarrow 25^{2^{p-1}} \equiv 25 \pmod{2^p+1} // Determine if N_p = (2^p + 1)/3 is prime for p > 2 var s = 25 var M = 2^p + 1 var N = M/3 repeat p - 1 times: s = (s × s) mod M if s == 25 return PRIME else return COMPOSITE == Known Wagstaff primes ==

The first few Wagstaff primes are: :3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... 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, ... == Generalizations ==

It is natural to consider more generally numbers of the form :Q(b,n)=\frac{b^n+1}{b+1} where the base b \ge 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 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. ), 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. ), 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, … , and these ns are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... . 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, ... 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, ... == References ==