A039772 -id:A039772 - cp's OEIS frontend

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

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

Karsten Meyer, Nov 12 2010

nonn

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

			15 is Fermat pseudoprime to base 4 and 11, so it is a Fermat pseudoprime.

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 Weisstein's World of Mathematics, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A039769, A181781, A211455, A211456, A211457, A211458, A227180, A280199.

Even terms give A039772. - Thomas Ordowski, Dec 28 2016

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 *)

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

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

Rexx
```
See Meyer link.
```

For any odd a(m), a(m) = A211456(m) + A211457(m). - Thomas Ordowski, Dec 09 2013

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

A209211 Numbers n such that n-1 and phi(n) are relatively prime.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138

Offset: 1

José María Grau Ribas, Mar 06 2012

nonn

A063994(a(n)) = 1. - Reinhard Zumkeller, Mar 02 2013
a(n) = A111305(n-2) for n >= 3. - Emmanuel Vantieghem, Jul 03 2013
n such that A049559(n) = 1.  Includes A100484 and A000079. - Robert Israel, Nov 09 2015
All terms except the first one are even. Missing even terms are A039772. - Robert G. Wilson v, Sep 26 2016
Numbers n such that A187730(n) = 1. - Thomas Ordowski, Dec 29 2016

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000010, A000079, A003277, A039772, A049559, A063994, A100484, A111305.

a209211 n = a209211_list !! (n-1)
a209211_list = filter (\x -> (x - 1) `gcd` a000010 x == 1) [1..]
-- Reinhard Zumkeller, Mar 02 2013

select(n -> igcd(n-1, numtheory:-phi(n)) = 1, [$1..1000]); # Robert Israel, Nov 09 2015

Select[Range[200], GCD[# - 1, EulerPhi[#]] == 1 &]

isok(n) = gcd(n-1, eulerphi(n)) == 1; \\ Michel Marcus, Sep 26 2016

A280199 Numbers n such that a^(n-1) == 1 (mod n^2) has solutions with 1 < a < n^2-1.

Original entry on oeis.org

5, 7, 11, 13, 15, 17, 19, 21, 23, 25, 28, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 52, 53, 55, 57, 59, 61, 63, 65, 66, 67, 69, 70, 71, 73, 75, 76, 77, 79, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 112, 113, 115, 117, 119, 121, 123, 124, 125

Offset: 1

Robert Israel and Thomas Ordowski, Dec 28 2016

nonn

Numbers n such that A185103(n) < n^2 + (-1)^n.
Complement of A280196.
Even terms are A039772.
Odd terms are all odd numbers that are not powers of 3.
Conjecture: composite terms are A181780.

			a(4) = 13 is in the sequence because 19^12 == 1 (mod 13^2), and 1 < 19 < 13^2-1.

Robert Israel, Table of n, a(n) for n = 1..17948

Cf. A000244, A039772, A185103, A280196.

Aeven:= remove(t -> igcd(t-1, numtheory:-phi(t^2))=1, {seq(i,i=2..1000,2)}):
Aodd:= {seq(i,i=3..1000,2)} minus {seq(3^i,i=0..floor(log[3](1000)))}:
sort(convert(Aeven union Aodd,list));

Aeven = DeleteCases[Range[2, 1000, 2], t_ /; GCD[t-1, EulerPhi[t^2]] == 1];
Aodd = Complement[Range[3, 1000, 2], Table[3^i, {i, 0, Floor[Log[3, 1000]]} ]];
Union[Aeven, Aodd] (* Jean-François Alcover, Apr 24 2019, after Robert Israel *)

A111305 Composite numbers k such that a^(k-1) == 1 (mod k) only when a == 1 (mod k).

Original entry on oeis.org

4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138, 140, 142, 144

Offset: 1

Karsten Meyer, Nov 02 2005

nonn

These unCarmichael numbers fail the Fermat primality test as often as possible.
All such numbers are even: for odd n, (-1)^(n-1) = 1.
The even numbers not in this sequence are 2 and A039772.
If c is a Carmichael number, then 2c is in the sequence. Also, the sequence is A209211 without the first two terms. - Emmanuel Vantieghem, Jul 03 2013

			10 is a term because 3^9 == 3 (mod 10), 7^9 == 7 (mod 10), 9^9 == 9 (mod 10).

Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.

Cf. A002997, A039772, A209211, A227180.

Select[Range[4, 144],Count[Table[PowerMod[b, # - 1, #], {b, 1, # - 1}], 1] == 1 &] (* Geoffrey Critzer, Apr 11 2015 *)

is(n)=for(a=2,n-1, if(Mod(a,n)^(n-1)==1, return(0))); !isprime(n) \\ Charles R Greathouse IV, Dec 22 2016

Edited by Don Reble, May 16 2006

A216412 The cubes arising in A039771.

Original entry on oeis.org

1, 1, 8, 8, 8, 8, 8, 64, 64, 64, 64, 64, 64, 64, 64, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 216, 512, 216, 216, 512, 512, 512, 1000, 1000, 512, 512, 1000, 512, 512, 512, 1728, 1728, 1000, 512, 1000, 512, 1728, 1000, 1728, 1728, 1000, 1000, 1728, 1728, 1000, 1728, 1728, 1000, 1728

Offset: 1

V. Raman, Sep 07 2012

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A039770, A039771, A039772, A062732, A078164, A166955.

Select[EulerPhi @ Range[3000], IntegerQ[Surd[#, 3]] &] (* Amiram Eldar, Mar 06 2020 *)

a(n) = A000010(A039771(n)). - Amiram Eldar, Mar 06 2020

A348259 Number of bases 1

Original entry on oeis.org

0, 0, 1, 0, 3, 0, 5, 0, 1, 0, 9, 0, 11, 0, 3, 0, 15, 0, 17, 0, 3, 0, 21, 0, 3, 0, 1, 2, 27, 0, 29, 0, 3, 0, 3, 0, 35, 0, 3, 0, 39, 0, 41, 0, 7, 0, 45, 0, 5, 0, 3, 2, 51, 0, 3, 0, 3, 0, 57, 0, 59, 0, 3, 0, 15, 4, 65, 0, 3, 2, 69, 0, 71, 0, 3

Offset: 1

Robert G. Wilson v, Oct 08 2021

This is a count of Fermat Pseudoprimes.
Numbers not in the sequence: 13, 25, 33, 37, 43, 49, 53, 61, 67, 73, 75, 83, 85, 89, 91, 93, 97, ..., .
First occurrence of k=0..: 1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, -1, 286, 17, 1854, ..., .

			a(3) = 1 since 2^3 = 8 == 2 (mod 3);
a(5) = 2 since {2, 3, 4}^5 = {32, 243, 1024} == {2, 3, 4} (mod 5);
a(9) = 1 since 8^9 = 134217728 == 8;
a(15) = 3 since {4, 11, 14}^15 = {1073741824, 4177248169415651, 155568095557812224} == {4, 11, 14} (mod 15); etc.

Antti Karttunen, Table of n, a(n) for n = 1..20000

Cf. A000040, A039772, A063994.

a[n_] := Length@ Select[Range[2, n -1], CoprimeQ[#, n] && PowerMod[#, n, n] == # &]; Array[a, 75]

a(n) = sum(b=2, n-1, if (gcd(b, n)==1, Mod(b, n)^n == b)); \\ Michel Marcus, Oct 09 2021

a(n) = A063994(n)-1.
a(2n) must be even. Those that exceed 0 are A039772.
a(p) = p-2 iff p is a prime (A000040).
a(2n-1) < 2n-3 iff 2n-1 is composite and a(2n-1) is odd.
a(n) = (Product_{primes p|n} gcd(p-1, n-1)) - 1. - Jianing Song, Nov 20 2021

A216452 The fourth roots of the fourth powers arising in A078164.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 10, 8, 8, 8, 10, 8, 10, 8, 8, 8, 10, 10, 10, 12, 12, 12, 12, 10, 12

Offset: 1

V. Raman, Sep 07 2012

nonn

Cf. A039770, A039771, A039772, A062732, A078164, A166955.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Rexx

Formula

Extensions

A209211 Numbers n such that n-1 and phi(n) are relatively prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A280199 Numbers n such that a^(n-1) == 1 (mod n^2) has solutions with 1 < a < n^2-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A111305 Composite numbers k such that a^(k-1) == 1 (mod k) only when a == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A216412 The cubes arising in A039771.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A348259 Number of bases 1

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A216452 The fourth roots of the fourth powers arising in A078164.

Views

Author

Keywords

Crossrefs