|
%I M5441 N2365 #224 Feb 24 2024 11:05:44
%S 341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,
%T 4371,4681,5461,6601,7957,8321,8481,8911,10261,10585,11305,12801,
%U 13741,13747,13981,14491,15709,15841,16705,18705,18721,19951,23001,23377,25761,29341
%N Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.
%C A composite number n is a Fermat pseudoprime to base b if and only if b^(n-1) == 1 (mod n). Fermat pseudoprimes to base 2 are often simply called pseudoprimes.
%C Theorem: If both numbers q and 2q - 1 are primes (q is in the sequence A005382) and n = q*(2q-1) then 2^(n-1) == 1 (mod n) (n is in the sequence) if and only if q is of the form 12k + 1. The sequence 2701, 18721, 49141, 104653, 226801, 665281, 721801, ... is related. This subsequence is also a subsequence of the sequences A005937 and A020137. - _Farideh Firoozbakht_, Sep 15 2006
%C Also, composite odd numbers n such that n divides 2^n - 2 (cf. A006935). It is known that all primes p divide 2^(p-1) - 1. There are only two known numbers n such that n^2 divides 2^(n-1) - 1, A001220(n) = {1093, 3511} Wieferich primes p: p^2 divides 2^(p-1) - 1. 1093^2 and 3511^2 are the terms of a(n). - _Alexander Adamchuk_, Nov 06 2006
%C An odd composite number 2n + 1 is in the sequence if and only if multiplicative order of 2 (mod 2n+1) divides 2n. - _Ray Chandler_, May 26 2008
%C The Carmichael numbers A002997 are a subset of this sequence. For the Sarrus numbers which are not Carmichael numbers, see A153508. - _Artur Jasinski_, Dec 28 2008
%C An odd number n greater than 1 is a Fermat pseudoprime to base b if and only if ((n-1)! - 1)*b^(n-1) == -1 (mod n). - _Arkadiusz Wesolowski_, Aug 20 2012
%C The name "Sarrus numbers" is after Frédéric Sarrus, who, in 1819, discovered that 341 is a counterexample to the "Chinese hypothesis" that n is prime if and only if 2^n is congruent to 2 (mod n). - _Alonso del Arte_, Apr 28 2013
%C The name "Poulet numbers" appears in Monografie Matematyczne 42 from 1932, apparently because Poulet in 1928 produced a list of these numbers (cf. Miller, 1975). - _Felix Fröhlich_, Aug 18 2014
%C Numbers n > 2 such that (n-1)! + 2^(n-1) == 1 (mod n). Composite numbers n such that (n-2)^(n-1) == 1 (mod n). - _Thomas Ordowski_, Feb 20 2016
%C The only twin pseudoprimes up to 10^13 are 4369, 4371. - _Thomas Ordowski_, Feb 12 2016
%C Theorem (A. Rotkiewicz, 1965): (2^p-1)*(2^q-1) is a pseudoprime if and only if p*q is a pseudoprime, where p,q are different primes. - _Thomas Ordowski_, Mar 31 2016
%C Theorem (W. Sierpiński, 1947): if n is a pseudoprime (odd or even), then 2^n-1 is a pseudoprime. - _Thomas Ordowski_, Apr 01 2016
%C If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - _Thomas Ordowski_, Sep 05 2016
%C From _Amiram Eldar_, Jun 19 2021: (Start)
%C Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".
%C Erdős (1950) called them "almost primes".
%C According to Erdős (1949) and Piza (1954), the term "pseudoprime" was coined by D. H. Lehmer.
%C Named after the French mathematician Pierre de Fermat (1607-1665), or, alternatively, after the Belgian mathematician Paul Poulet (1887-1946), or, the French mathematician Pierre Frédéric Sarrus (1798-1861). (End)
%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A12, pp. 44-50.
%D George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982), p. 22.
%D Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948.
%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).
%H N. J. A. Sloane, <a href="/A001567/b001567.txt">Table of n, a(n) for n = 1..101629</a> [The pseudoprimes up to 10^12, from Richard Pinch's web site - see links below]
%H Jonathan Bayless and Paul Kinlaw, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Bayless/bayless3.html">Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4.
%H Jens Bernheiden, <a href="https://web.archive.org/web/20160508153313/http://www.mathe-schule.de/download/pdf/Primzahl/PSP.pdf">Pseudoprimes</a> (Text in German).
%H John Brillhart, N. J. A. Sloane, J. D. Swift, <a href="/A001567/a001567_2.pdf">Correspondence, 1972</a>.
%H Paul Erdős, <a href="https://www.jstor.org/stable/2304732">On the converse of Fermat's theorem</a>, The American Mathematical Monthly, Vol. 56, No. 9 (1949), pp. 623-624; <a href="https://users.renyi.hu/~p_erdos/1949-07.pdf">alternative link</a>.
%H Paul Erdős, <a href="https://www.jstor.org/stable/2307640">On almost primes</a>, Amer. Math. Monthly, Vol. 57, No. 6 (1950), pp. 404-407; <a href="https://users.renyi.hu/~p_erdos/1950-06.pdf">alternative link</a>.
%H Jan Feitsma, <a href="https://web.archive.org/web/20130316150225/http://www.janfeitsma.nl/math/psp2/index">The pseudoprimes below 2^64</a>.
%H William Galway, <a href="http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html">Tables of pseudoprimes and related data</a> [Includes a file with pseudoprimes up to 2^64.]
%H Richard K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]
%H Paul Kinlaw, <a href="https://doi.org/10.1090/mcom/3933">The reciprocal sums of pseudoprimes and Carmichael numbers</a>, Mathematics of Computation (2023).
%H D. H. Lehmer, <a href="https://www.nap.edu/read/18678/chapter/3#47">Guide to Tables in the Theory of Numbers</a>, Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 48.
%H D. H. Lehmer, <a href="http://www.jstor.org/stable/2004371">Errata for Poulet's table</a>, Math. Comp., Vol. 25, No. 116 (1971), pp. 944-945.
%H D. H. Lehmer, <a href="/A001567/a001567_1.pdf">Errata for Poulet's table</a>. [annotated scanned copy]
%H Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm">Pseudoprimes</a>.
%H J. C. P. Miller, <a href="http://dx.doi.org/10.1090/S0025-5718-1975-0366796-6">On factorization, with a suggested new approach</a>, Math. Comp., Vol. 29, No. 129 (1975), pp. 155-172. - _Felix Fröhlich_, Aug 18 2014
%H Robert Morris, <a href="/A001567/a001567.pdf">Some observations on the converse of Fermat's theorem</a>, unpublished memorandum, Oct 03 1973.
%H Richard Pinch, <a href="http://www.chalcedon.demon.co.uk/rgep/carpsp.html">Pseudoprimes</a>.
%H P. A. Piza, <a href="https://www.jstor.org/stable/3029103">Fermat Coefficients</a>, Mathematics Magazine, Vol. 27, No. 3 (1954), pp. 141-146.
%H Carl Pomerance & N. J. A. Sloane, <a href="/A001567/a001567_4.pdf">Correspondence, 1991</a>.
%H Paul Poulet, <a href="/A001567/a001567_3.pdf">Tables des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu'à 100.000.000</a>, Sphinx (Brussels), Vol. 8 (1938), pp. 42-45. [annotated scanned copy]
%H Fred Richman, <a href="http://math.fau.edu/Richman/carm.htm">Primality testing with Fermat's little theorem</a>.
%H Andrzej Rotkiewicz, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002075660">Sur les nombres pseudopremiers de la forme MpMq</a>, Elemente der Mathematik, Vol. 20 (1965), pp. 108-109.
%H Waclaw Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm1/cm113.pdf">Remarque sur une hypothèse des Chinois concernant les nombres (2^n-2)/n</a>, Colloquium Mathematicum, Vol. 1 (1947), p. 9.
%H Waclaw Sierpiński, <a href="http://matwbn.icm.edu.pl/kstresc.php?tom=42&wyd=10">Elementary Theory of Numbers</a>, Państ. Wydaw. Nauk., Warszawa, 1964, p. 215.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChineseHypothesis.html">Chinese Hypothesis</a>, <a href="http://mathworld.wolfram.com/FermatPseudoprime.html">Fermat Pseudoprime</a>, <a href="http://mathworld.wolfram.com/PouletNumber.html">Poulet Number</a>, and <a href="http://mathworld.wolfram.com/Pseudoprime.html">Pseudoprime</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Chinese_hypothesis">Chinese hypothesis</a> and <a href="http://en.wikipedia.org/wiki/Pseudoprime">Pseudoprime</a>.
%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%F Sum_{n>=1} 1/a(n) is in the interval (0.015260, 33) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0911 by Kinlaw (2023). - _Amiram Eldar_, Oct 15 2020, Feb 24 2024
%p select(t -> not isprime(t) and 2 &^(t-1) mod t = 1, [seq(i,i=3..10^5,2)]); # _Robert Israel_, Feb 18 2016
%t Select[Range[3,30000,2], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] (* _Farideh Firoozbakht_, Sep 15 2006 *)
%o (PARI) q=1;vector(50,i,until( !isprime(q) & (1<<(q-1)-1)%q == 0, q+=2);q) \\ _M. F. Hasler_, May 04 2007
%o (PARI) is_A001567(n)={Mod(2,n)^(n-1)==1 && !isprime(n) && n>1} \\ _M. F. Hasler_, Oct 07 2012, updated to current PARI syntax and to exclude even pseudoprimes on Mar 01 2019
%o (Magma) [n: n in [3..3*10^4 by 2] | IsOne(Modexp(2,n-1,n)) and not IsPrime(n)]; // _Bruno Berselli_, Jan 17 2013
%Y Cf. A002997, A005382, A020137, A052155, A083737, A084653, A153508.
%Y Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.
%Y Cf. A005935, A005936, A005937, A005938, A005939, A020136-A020228 (pseudoprimes to bases 3 through 100).
%K nonn,nice
%O 1,1
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_, Aug 15 1996
%E Replacement of broken geocities link by _Jason G. Wurtzel_, Sep 05 2010
%E "Poulet numbers" added to name by _Joerg Arndt_, Aug 18 2014
|
