A000978 - OEIS

%I M2413 N0956 #131 Aug 23 2024 12:16:59

%S 3,5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,

%T 1709,2617,3539,5807,10501,10691,11279,12391,14479,42737,83339,95369,

%U 117239,127031,138937,141079,267017,269987,374321,986191,4031399

%N Wagstaff numbers: numbers k such that (2^k + 1)/3 is prime.

%C It is easy to see that the definition implies that k must be an odd prime. - _N. J. A. Sloane_, Oct 06 2006

%C The terms from a(32) on only give probable primes as of 2018. Caldwell lists the largest certified primes. - _Jens Kruse Andersen_, Jan 10 2018

%C Prime numbers of the form 1+Sum_{i=1..m} 2^(2i-1). - _Artur Jasinski_, Feb 09 2007

%C There is a new conjecture stating that a Wagstaff number is prime under the following condition (based on DiGraph cycles under the LLT): Let p be a prime integer > 3, N(p) = 2^p+1 and W(p) = N(p)/3, S(0) = 3/2 (or 1/4) and S(i+1) = S(i)^2 - 2 (mod N(p)). Then W(p) is prime iff S(p-1) == S(0) (mod W(p)). - _Tony Reix_, Sep 03 2007

%C As a member of the DUR team (Diepeveen, Underwood, Reix), and thanks to the LLR tool built by Jean Penne, I've found a new and big Wagstaff PRP: (2^4031399+1)/3 is Vrba-Reix PRP! This Wagstaff number has 1,213,572 digits and today is the 3rd biggest PRP ever found. I've done a second verification on a Nehalem core with the PFGW tool. - _Tony Reix_, Feb 20 2010

%C 13347311 and 13372531 were found to be terms of this sequence (maybe not the next ones) by _Ryan Propper_ in September 2013. - _Max Alekseyev_, Oct 07 2013

%C The next term is larger than 10 million. - _Gord Palameta_, Mar 22 2019

%C Ryan Propper found another likely term, 15135397, though it only corresponds to a probable prime. - _Charles R Greathouse IV_, Jul 01 2021

%D J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D S. S. Wagstaff, Jr., personal communication.

%H J. Brillhart et al., <a href="http://dx.doi.org/10.1090/conm/022">Factorizations of b^n +- 1</a>, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.

%H C. Caldwell's The Top Twenty, <a href="https://t5k.org/top20/page.php?id=67">Wagstaff</a>.

%H C. Caldwell, <a href="https://t5k.org/mersenne/NewMersenneConjecture.html">New Mersenne Conjecture</a>

%H H. Dubner, <a href="/A028491/a028491.pdf">Generalized repunit primes</a>, Math. Comp., 61 (1993), 927-930. [Annotated scanned copy]

%H H. Dubner and T. Granlund, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.html">Primes of the Form (b^n+1)/(b+1)</a>, J. Integer Sequences, 3 (2000), #P00.2.7.

%H Editor's Note, <a href="/A000979/a000979.pdf">Table of Wagstaff primes sent by D. H. Lehmer</a> (annotated and scanned copy)

%H J. E. Foster, <a href="http://www.jstor.org/stable/3029104">Problem 174, A solution in primes</a>, Math. Mag., 27 (1954), 156-157.

%H R. K. Guy, <a href="/A000978/a000978.pdf">Letter to N. J. A. Sloane, Aug 1986</a>

%H R. K. Guy, <a href="/A005728/a005728.pdf">Letter to N. J. A. Sloane, 1987</a>

%H H. Lifchitz, <a href="http://www.primenumbers.net/Henri/us/MersFermus.htm">Mersenne and Fermat primes field</a>

%H H. & R. Lifchitz, <a href="http://www.primenumbers.net/prptop/searchform.php?form=%282%5En%2B1%29%2F3&amp;action=Search">PRP Top Records</a>.

%H Henri & Renaud Lifchitz, <a href="http://www.primenumbers.net/prptop/prptop.php">PRP Records.</a>

%H Gord Palameta, <a href="https://mersenneforum.org/showthread.php?t=24185">There are no new Wagstaff primes with exponent below 10 million</a>, mersenneforum.org

%H Ryan Propper et al., <a href="http://mersenneforum.org/showthread.php?t=18569">New Wagstaff PRP exponents</a>, mersenneforum.org

%H PRP top list: <a href="http://www.primenumbers.net/prptop/prptop.php?page=1#haut">PRP top</a> [From _Tony Reix_, Feb 20 2010]

%H Tony Reix, <a href="http://www.worldofnumbers.com/YPFM10184.htm">Yahoo Primeform Group Message 10184 dd. Feb 20, 2010</a>, reconstruction in html.

%H T. Reix, <a href="http://trex58.wordpress.com/math2matiques/">Some Maths about the Vrba-Reix PRP test</a> [From _Tony Reix_, Feb 20 2010]

%H Djurre G. Sikkema, <a href="https://fse.studenttheses.ub.rug.nl/33908">Probable primality testing for Wagstaff prime</a>, Bachelor's project mathematics, Univ. Groningen (Netherlands 2024). See p. 32.

%H S. S. Wagstaff, Jr., <a href="http://www.cerias.purdue.edu/homes/ssw/cun/index.html">The Cunningham Project</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Repunit.html">Repunit</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WagstaffPrime.html">Wagstaff Prime</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerSequencePrimes.html">Integer Sequence Primes</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Wagstaff_prime">Wagstaff prime</a>

%H R. G. Wilson, v, <a href="/A084740/a084740.pdf">Letter to N. J. A. Sloane, circa 1991.</a>

%F a(n) = A107036(n) for n>1. - _Alexander Adamchuk_, Feb 10 2007

%t Select[Range[5000], PrimeQ[(2^# + 1)/3] &] (* _Michael De Vlieger_, Jan 10 2018 *)

%t Select[Prime[Range[2,500]],PrimeQ[(2^#+1)/3]&] (* _Harvey P. Dale_, Jun 13 2022 *)

%o (PARI) forprime(p=2,5000,if(ispseudoprime(2^p\/3),print1(p", "))) \\ _Charles R Greathouse IV_, Jul 15 2011

%o (Haskell)

%o a000978 n = a000978_list !! (n-1)

%o a000978_list = filter ((== 1) . a010051 . a001045) a065091_list

%o -- _Reinhard Zumkeller_, Mar 24 2013

%o (Python)

%o from gmpy2 import divexact

%o from sympy import prime, isprime

%o A000978 = [p for p in (prime(n) for n in range(2,10**2)) if isprime(divexact(2**p+1,3))] # _Chai Wah Wu_, Sep 04 2014

%Y Cf. A107036 (indices of prime Jacobsthal numbers).

%Y Cf. A000979, A124400, A124401, A127955, A127956, A127957, A127958, A127936, A010051, A065091, A001045.

%K nonn,hard,nice,more

%O 1,1

%A _N. J. A. Sloane_, _Robert G. Wilson v_

%E a(30) from Kamil Duszenko (kdusz(AT)wp.pl), Feb 03 2003; a(30) was proved prime by Francois Morain with FastECPP. - _Tony Reix_, Sep 03 2007

%E a(31)-a(39) from _Robert G. Wilson v_, Apr 11 2005

%E a(40) from Vincent Diepeveen (diep(AT)xs4all.nl) added by _Alexander Adamchuk_, Jun 19 2008

%E a(41) from _Tony Reix_, Feb 20 2010