OFFSET
1,1
COMMENTS
A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n).
LINKS
Karsten Meyer and T. D. Noe, Table of n, a(n) for n = 1..10000 (first 5978 terms from Karsten Meyer)
Karsten Meyer, Tabelle Pseudoprimzahlen (15-4999)
Karsten Meyer, Rexx program for this sequence
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
FORMULA
EXAMPLE
15 is Fermat pseudoprime to base 4 and 11, so it is a Fermat pseudoprime.
MATHEMATICA
t = {}; Do[s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, n]], {n, Select[Range[213], ! PrimeQ[#] &]}]; t (* T. D. Noe, Nov 07 2011 *)
(* The following program is much faster than the one above. See A227180 for indications of a proof of this assertion. *) Select[Range[213], ! IntegerQ[Log[3, #]] && ! PrimeQ[#] && GCD[# - 1, EulerPhi[#]] > 1 &] (* Emmanuel Vantieghem, Jul 06 2013 *)
PROG
(Rexx) See Meyer link.
(PARI)
fsp(n)=
{ /* whether n is Fermat pseudoprime to any base a where 2<=a<=n-2 */
for (a=2, n-2,
if ( gcd(a, n)!=1, next() );
if ( (Mod(a, n))^(n-1)==+1, return(1) )
);
return(0);
}
for(n=3, 300, if(isprime(n), next()); if ( fsp(n) , print1(n, ", ") ); );
\\ Joerg Arndt, Jan 08 2011
(PARI) is(n)=if(isprime(n), return(0)); my(f=factor(n)[, 1]); prod(i=1, #f, gcd(f[i]-1, n-1)) > 2 \\ Charles R Greathouse IV, Dec 28 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Karsten Meyer, Nov 12 2010
EXTENSIONS
Used a comment line to give a more explicit definition. - N. J. A. Sloane, Nov 12 2010
Definition corrected by Max Alekseyev, Nov 12 2010
STATUS
approved