cp's OEIS Frontend

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

%I A181780 #128 Feb 16 2025 08:33:13
%S A181780 15,21,25,28,33,35,39,45,49,51,52,55,57,63,65,66,69,70,75,76,77,85,87,
%T A181780 91,93,95,99,105,111,112,115,117,119,121,123,124,125,129,130,133,135,
%U A181780 141,143,145,147,148,153,154,155,159,161,165,169,171,172,175,176
%N A181780 Numbers n which are Fermat pseudoprimes to some base b, 2 <= b <= n-2.
%C A181780 A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n).
%C A181780 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
%H A181780 Karsten Meyer and T. D. Noe, <a href="/A181780/b181780.txt">Table of n, a(n) for n = 1..10000</a> (first 5978 terms from Karsten Meyer)
%H A181780 Karsten Meyer, <a href="http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_%2815_-_4999%29">Tabelle Pseudoprimzahlen (15-4999)</a>
%H A181780 Karsten Meyer, <a href="/A181780/a181780.rexx.txt">Rexx program for this sequence</a>
%H A181780 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FermatPseudoprime.html">Fermat Pseudoprime</a>
%H A181780 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%F A181780 For any odd a(m), a(m) = A211456(m) + A211457(m). - _Thomas Ordowski_, Dec 09 2013
%e A181780 15 is Fermat pseudoprime to base 4 and 11, so it is a Fermat pseudoprime.
%t A181780 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 *)
%t A181780 (* 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 *)
%o A181780 (Rexx) See Meyer link.
%o A181780 (PARI)
%o A181780 fsp(n)=
%o A181780 { /* whether n is Fermat pseudoprime to any base a where 2<=a<=n-2 */
%o A181780     for (a=2,n-2,
%o A181780         if ( gcd(a,n)!=1, next() );
%o A181780         if ( (Mod(a,n))^(n-1)==+1, return(1) )
%o A181780     );
%o A181780     return(0);
%o A181780 }
%o A181780 for(n=3,300, if(isprime(n),next());  if ( fsp(n) , print1(n,", ") ); );
%o A181780 \\ _Joerg Arndt_, Jan 08 2011
%o A181780 (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
%Y A181780 Cf. A039769, A181781, A211455, A211456, A211457, A211458, A227180, A280199.
%Y A181780 Even terms give A039772. - _Thomas Ordowski_, Dec 28 2016
%K A181780 nonn
%O A181780 1,1
%A A181780 _Karsten Meyer_, Nov 12 2010
%E A181780 Used a comment line to give a more explicit definition. - _N. J. A. Sloane_, Nov 12 2010
%E A181780 Definition corrected by _Max Alekseyev_, Nov 12 2010