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!)
A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers.
(Formerly M5441 N2365)
238
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 the 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 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

REFERENCES

R. K. Guy, Unsolved Problems Theory of Numbers, A12.

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 48.

George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982): 22.

P. Poulet, Tables des nombres composes verifiant le theoreme de Fermat pour le module 2 jusqu'a 100.000.000, Sphinx (Brussels), 8 (1938), 42-45.

W. Sierpiński, Elementary Theory of Numbers. Państ. Wydaw. Nauk., Warsaw, 1964, p. 215.

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

N. J. A. Sloane, Table of n, a(n) for n = 1..101629 [The pseudoprimes up to 10^12, from Richard Pinch's web site - see links below]

J. Bernheiden, Pseudoprimes (Text in German)

J. Feitsma, The pseudoprimes below 2^64

W. Galway, Tables of pseudoprimes and related data [Includes a file with pseudoprimes up to 2^64.]

D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945. 25 944 1971.

G. P. Michon, Pseudoprimes

Richard Pinch, Pseudoprimes

F. Richman, Primality testing with Fermat's little theorem

W. Sierpi\'{n}ski, Elementary Theory of Numbers, Warszawa 1964.

Eric Weisstein's World of Mathematics, Chinese Hypothesis

Eric Weisstein's World of Mathematics, Poulet Number

Eric Weisstein's World of Mathematics, Pseudoprime

Eric Weisstein's World of Mathematics, Fermat Pseudoprime

Wikipedia, Pseudoprime

Wikipedia, Chinese hypothesis

Index entries for sequences related to pseudoprimes

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==2 & !isprime(n) & n>1}  \\ M. F. Hasler, Oct 07 2012

(MAGMA) [n: n in [3..3*10^4 by 2] | IsOne(2^(n-1) mod n) and not IsPrime(n)]; // Bruno Berselli, Jan 17 2013

CROSSREFS

Cf. A002997, A052155, A083737, A084653, A005382, A020137.

Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.

Cf. A153508.

Cf. A005935, A005936, A005937, A005938, A005939, A020136-A020228 (pseudoprimes for bases 3 to 100).

Sequence in context: A020188 A025353 A025345 * A178723 A210993 A006970

Adjacent sequences:  A001564 A001565 A001566 * A001568 A001569 A001570

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from David W. Wilson, Aug 15 1996.

Replacement of broken geocities link by Jason G. Wurtzel, Sep 05 2010

STATUS

approved

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 July 28 00:26 EDT 2014. Contains 244987 sequences.