

A181780


Numbers n which are Fermat pseudoprimes to some base b, 2 <= b <= n2.


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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

A nonprime number n is a Fermat pseudoprime to base b if b^(n1) = 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)
Karsten Meyer, Tabelle Pseudoprimzahlen (154999)
Karsten Meyer, Rexx program for this sequence
Eric W. Weisstein, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes


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, n2], PowerMod[#, n1, 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<=n2 */
for (a=2, n2,
if ( gcd(a, n)!=1, next() );
if ( (Mod(a, n))^(n1)==+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, n1)) > 2 \\ Charles R Greathouse IV, Dec 28 2016


CROSSREFS

Cf. A039769, A181781, A211455, A211456, A211457, A211458, A227180, A280199.
Even terms give A039772.  Thomas Ordowski, Dec 28 2016
Sequence in context: A325037 A154545 A156063 * A273061 A129926 A020204
Adjacent sequences: A181777 A181778 A181779 * A181781 A181782 A181783


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



