login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

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 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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^(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)

Karsten Meyer, Tabelle Pseudoprimzahlen (15-4999)

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, 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 23:44 EST 2022. Contains 358485 sequences. (Running on oeis4.)