login
This site is supported by donations to The OEIS Foundation.

 

Logo


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. 13
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: A177024 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 17:44 EST 2019. Contains 319349 sequences. (Running on oeis4.)