login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1. 79

%I

%S 1093,3511

%N Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1.

%C Sequence is believed to be infinite.

%C Joseph Silverman showed that the abc-conjecture implies that there are infinitely many primes which are not in the sequence. - _Benoit Cloitre_, Jan 09 2003

%C Graves and Murty (2013) improved Silverman's result by showing that for any fixed k > 1, the abc-conjecture implies that there are infinitely many primes == 1 (mod k) which are not in the sequence. - _Jonathan Sondow_, Jan 21 2013

%C The squares of these numbers are Fermat pseudoprimes to base 2 (A001567) and Catalan pseudoprimes (A163209). - _T. D. Noe_, May 22 2003

%C Primes p that divide the numerator of the harmonic number H((p-1)/2); that is, p divides A001008((p-1)/2). - _T. D. Noe_, Mar 31 2004

%C In a 1977 paper, Wells Johnson, citing a suggestion from Lawrence Washington, pointed out the repetitions in the binary representations of the numbers which are one less than the two known Wieferich primes; i.e., 1092 = 10001000100 (base 2); 3510 = 110110110110 (base 2). It is perhaps worth remarking that 1092 = 444 (base 16) and 3510 = 6666 (base 8), so that these numbers are small multiples of repunits in the respective bases. Whether this is mathematically significant does not appear to be known. - _John Blythe Dobson_, Sep 29 2007

%C A002326((a(n)^2 - 1)/2) = A002326((a(n)-1)/2). - _Vladimir Shevelev_, Jul 09 2008, Aug 24 2008

%C It is believed that p^2 does not divide 3^(p-1) - 1 if p = a(n). This is true for n = 1 and 2. See A178815, A178844, A178900, and Ostafe-Shparlinski (2010) Section 1.1. - _Jonathan Sondow_, Jun 29 2010

%C These primes also divide the numerator of the harmonic number H(floor((p-1)/4)). - H. Eskandari (hamid.r.eskandari(AT)gmail.com), Sep 28 2010

%C 1093 and 3511 are prime numbers p satisfying congruence 429327^(p-1) == 1 (mod p^2). Why? - _Arkadiusz Wesolowski_, Apr 07 2011

%C A196202(A049084(a(1)) = A196202(A049084(a(2)) = 1. - _Reinhard Zumkeller_, Sep 29 2011

%C If q is prime and q^2 divides a prime-exponent Mersenne number, then q must be a Wieferich prime. Neither of the two known Wieferich primes divide Mersenne numbers. See Will Edgington's Mersenne page in the links below. - _Daran Gill_, Apr 04 2013

%C There are no other terms below 1.45*10^17 as established by PrimeGrid (see link below). - _Max Alekseyev_, Jul 14 2014

%D R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 28.

%D R. K. Guy, Unsolved Problems in Number Theory, A3.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 91.

%D Y. Hellegouarch, "Invitation aux mathematiques de Fermat Wiles", Dunod, 2eme Edition, pp. 340-341.

%D Pace Nielsen, Wieferich primes, heuristics, computations, Abstracts Amer. Math. Soc., 33 (#1, 20912), #1077-11-48.

%D P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 263.

%D D. Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 163.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.780

%H C. K. Caldwell, The Prime Glossary, <a href="http://www.utm.edu/research/primes/glossary/WieferichPrime.html">Wieferich prime</a>

%H C. K. Caldwell, <a href="http://primes.utm.edu/notes/proofs/SquareMerDiv.html">Prime-square Mersenne divisors are Wieferich</a>

%H D. X. Charles, <a href="http://www.cs.wisc.edu/~cdx/Criterion.pdf">On Wieferich Primes</a>

%H R. Crandall, K. Dilcher and C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/paper111.pdf">A search for Wieferich and Wilson primes</a>, Mathematics of Computation, Volume 66, 1997.

%H J. K. Crump, Joe's Number Theory Web, <a href="http://web.archive.org/web/20110728092734/http://www.immortaltheory.com/NumberTheory/Wieferich.htm">Weiferich Primes</a> (sic)

%H John Blythe Dobson, <a href="http://cybrary.uwinnipeg.ca/people/Dobson/mathematics/Wieferich_primes.html">A note on the two known Wieferich Primes</a>

%H F. G. Dorais, <a href="http://www.math.cornell.edu/~dorais/index.php?page=software">WPSE - A Wieferich Prime Search Engine</a> (A program to search Wieferich primes written by F. G. Dorais.) - _Felix Fröhlich_, Jul 13 2014

%H F. G. Dorais and D. W. Klyve, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html">A Wieferich Prime Search up to 6.7*10^15</a>, Journal of Integer Sequences, Vol. 14, 2011.

%H Will Edgington, <a href="http://www.garlic.com/~wedgingt/mersenne.html">Mersenne Page</a>.

%H A. Granville, K. Soundararajan, <a href="http://dx.doi.org/10.1023/A:1009786614584">A binary additive problem of Erdos and the order of 2 mod p^2</a>, Raman. J. 2 (1998) 283-298

%H Hester Graves and M. Ram Murty, <a href="http://www.mast.queensu.ca/~murty/Wieferich.pdf">The abc conjecture and non-Wieferich primes in arithmetic progressions</a>, Journal of Number Theory, 133 (2013), 1809-1813.

%H Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (<a href="http://math.berkeley.edu/~halbeis/publications/psf/seq.ps">ps</a>, <a href="http://math.berkeley.edu/~halbeis/publications/pdf/seq.pdf">pdf</a>)

%H W. Johnson, On the nonvanishing of Fermat quotients (mod p), <a href="http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN243919689_0292">Journal f. die Reine und Angewandte Mathematik 292</a> (1977): 196-200.

%H J. Knauer and J. Richstein, <a href="http://dx.doi.org/10.1090/S0025-5718-05-01723-0">The continuing search for Wieferich primes</a>, Math. Comp., 75 (2005), 1559-1563.

%H P. Lezak, <a href="http://sourceforge.net/projects/wieferich/">Software for searching Wieferich primes</a> - _Felix Fröhlich_, Jul 13 2014

%H C. McLeman, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/WieferichPrime.html">Wieferich prime</a>

%H Sihem Mesnager and Jean-Pierre Flori, <a href="http://eprint.iacr.org/2012/033.pdf">A note on hyper-bent functions via Dillon-like exponents</a>

%H A. Ostafe and I. Shparlinski (2010), <a href="http://arxiv.org/abs/1001.1504"> Pseudorandomness and Dynamics of Fermat Quotients</a>

%H Christian Perfect, <a href="http://aperiodical.com/2013/07/integer-sequence-reviews-on-numberphile-or-vice-versa/">Integer sequence reviews on Numberphile (or vice versa)</a>, 2013.

%H M. Rodenkirch, <a href="http://home.roadrunner.com/~mrodenkirch/home/PRPNet.html">PRPNet</a> (The PRPNet package includes wwww, a program that can search for Wieferich and Wall-Sun-Sun primes.) - _Felix Fröhlich_, Jul 13 2014

%H J. Silverman, <a href="http://dx.doi.org/10.1016/0022-314X(88)90019-4">Wieferich's Criterion and the abc Conjecture</a>, J. Number Th. 30 (1988) 226-237.

%H J. Sondow, <a href="http://arxiv.org/abs/1110.3113">Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771</a>, arXiv 2011.

%H PrimeGrid, <a href="http://prpnet.mine.nu:13000/">Wieferich Prime Search statistics</a>

%H V. Shevelev, <a href="http://arxiv.org/abs/0806.3412">Overpseudoprimes, Mersenne Numbers and Wieferich Primes</a>, arxiv:0806.3412

%H Michel Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/abcLahore032013.pdf">Lecture on the abc conjecture and some of its consequences</a>, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.

%H Michel Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/abcLahore2013VI.pdf">Lecture on the abc conjecture and some of its consequences</a>, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.

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

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

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

%H Wieferich Home Page, <a href="http://www.elmath.org/">Search for Wieferich primes</a>

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

%H P. Zimmermann, <a href="http://www.loria.fr/~zimmerma/records/primes.html">Records for Prime Numbers</a>

%F A178815(A000720(p))^(p-1) - 1 mod p^2 = A178900(n), where p = a(n). - _Jonathan Sondow_, Jun 29 2010

%F Odd primes p such that A002326((p^2-1)/2) = A002326((p-1)/2). See A182297. - _Thomas Ordowski_, Feb 04 2014

%p wieferich := proc (n) local nsq, remain, bin, char: if (not isprime(n)) then RETURN("not prime") fi: nsq := n^2: remain := 2: bin := convert(convert(n-1, binary),string): remain := (remain * 2) mod nsq: bin := substring(bin,2..length(bin)): while (length(bin) > 1) do: char := substring(bin,1..1): if char = "1"

%p then remain := (remain * 2) mod nsq fi: remain := (remain^2) mod nsq: bin := substring(bin,2..length(bin)): od: if (bin = "1") then remain := (remain * 2) mod nsq fi: if remain = 1 then RETURN ("Wieferich prime") fi: RETURN ("non-Wieferich prime"): end: # UlrSchimke(AT)aol.com, Nov 01, 2001

%t Select[Prime[Range[50000]],Divisible[2^(#-1)-1,#^2]&] (* _Harvey P. Dale_, Apr 23 2011 *)

%o (Haskell)

%o import Data.List (elemIndices)

%o a001220 n = a001220_list !! (n-1)

%o a001220_list = map (a000040 . (+ 1)) $ elemIndices 1 a196202_list

%o -- _Reinhard Zumkeller_, Sep 29 2011

%o (PARI)

%o N=10^9; default(primelimit,N);

%o forprime(n=2,N,if(Mod(2,n^2)^(n-1)==1,print1(n,", ")));

%o \\ _Joerg Arndt_, May 01 2013

%Y See A007540 for a similar problem.

%Y Sequences "primes p such that p^2 divides X^(p-1)-1": A014127 (X=3), A123692 (X=5), A212583 (X=6), A123693 (X=7), A045616 (X=10).

%Y Cf. A001567, A077816, A001008, A039951, A049094, A126196, A126197, A178815, A178844, A178871, A178900.

%K nonn,hard,bref,nice,more

%O 1,1

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 1 04:34 EDT 2014. Contains 247498 sequences.