login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A181780
Numbers n which are Fermat pseudoprimes to some base b, 2 <= b <= n-2.
14
15, 21, 25, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 130, 133, 135, 141, 143, 145, 147, 148, 153, 154, 155, 159, 161, 165, 169, 171, 172, 175, 176
OFFSET
1,1
COMMENTS
A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n).
It appears that these n are pseudoprimes for an even number of bases. When n is the product of two distinct primes, it appears that there are exactly two such bases x and y with x + y = n. See A211455, A211456, and A211457. - T. D. Noe, Apr 12 2012
LINKS
Karsten Meyer and T. D. Noe, Table of n, a(n) for n = 1..10000 (first 5978 terms from Karsten Meyer)
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
FORMULA
For any odd a(m), a(m) = A211456(m) + A211457(m). - Thomas Ordowski, Dec 09 2013
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
Even terms give A039772. - Thomas Ordowski, Dec 28 2016
Sequence in context: A325037 A154545 A156063 * A273061 A129926 A020204
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