|
| |
|
|
A001567
|
|
Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.
(Formerly M5441 N2365)
|
|
347
|
|
|
|
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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.
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
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
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
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
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
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
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
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
The only twin pseudoprimes up to 10^13 are 4369, 4371. - Thomas Ordowski, Feb 12 2016
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
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
If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - Thomas Ordowski, Sep 05 2016
Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".
Erdős (1950) called them "almost primes".
According to Erdős (1949) and Piza (1954), the term "pseudoprime" was coined by D. H. Lehmer.
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)
|
|
|
REFERENCES
|
Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A12, p. 44-50.
George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982), p. 22.
Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
Sum_{n>=1} 1/a(n) is in the interval (0.015260, 33) (Bayless and Kinlaw, 2017). - Amiram Eldar, Oct 15 2020
|
|
|
MAPLE
|
select(t -> not isprime(t) and 2 &^(t-1) mod t = 1, [seq(i, i=3..10^5, 2)]); # Robert Israel, Feb 18 2016
|
|
|
MATHEMATICA
|
Select[Range[3, 30000, 2], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 15 2006 *)
|
|
|
PROG
|
(PARI) q=1; vector(50, i, until( !isprime(q) & (1<<(q-1)-1)%q == 0, q+=2); q) \\ M. F. Hasler, May 04 2007
(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
(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
|
|
|
CROSSREFS
|
Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
"Poulet numbers" added to name by Joerg Arndt, Aug 18 2014
|
|
|
STATUS
|
approved
|
| |
|
|
