A181780 -id:A181780 - cp's OEIS frontend

A211455 The number of bases b for which A181780(n) is a Fermat pseudoprime.

2, 2, 2, 2, 2, 2, 2, 6, 4, 2, 2, 2, 2, 2, 14, 4, 2, 2, 2, 2, 2, 14, 2, 34, 2, 2, 2, 14, 2, 2, 2, 6, 2, 8, 2, 2, 2, 2, 2, 34, 2, 2, 2, 14, 2, 2, 14, 2, 2, 2, 2, 14, 10, 2, 2, 10, 4, 2, 2, 14, 4, 2, 2, 8, 6, 2, 2, 2, 14, 2, 2, 2, 2, 2, 34, 2, 14, 6, 38, 6, 2, 2

Offset: 1

T. D. Noe, Apr 13 2012

nonn

Sequences A211456 and A211457 give the smallest and largest bases b; A211458 lists all bases.

Every term in this sequence is even. - Geoffrey Critzer, Apr 08 2015

Cf. A181780, A211456, A211457, A211458.

t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n], s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, {n, Length[s], s}]]]]; Transpose[t][[2]]
f[n_] := If[ PrimeQ@ n, {}, Count[ Table[ PowerMod[k, n - 1, n], {k, 2, n - 2}], 1]] /. {0 -> {}}; Array[f, 237] // Flatten (* Robert G. Wilson v, Apr 08 2015 *)

a(n) = A063994(m) - 2 for odd m in A181780. a(n) = A063994(m) - 1 for even m in A181780. - Thomas Ordowski, Dec 13 2013

A211456 Smallest base b for which A181780(n) is a Fermat pseudoprime.

Original entry on oeis.org

4, 8, 7, 9, 10, 6, 14, 8, 18, 16, 9, 21, 20, 8, 8, 25, 22, 11, 26, 45, 34, 4, 28, 3, 32, 39, 10, 8, 38, 65, 24, 8, 50, 3, 40, 5, 57, 44, 61, 8, 26, 46, 12, 12, 50, 121, 8, 23, 61, 52, 22, 23, 19, 37, 49, 24, 49, 58, 62, 6, 97, 67, 55, 11, 14, 165, 68, 57, 9

Offset: 1

T. D. Noe, Apr 13 2012

nonn

That is, the smallest b for which b^(s-1) = 1 (mod s), where s is in A181780.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A181780, A211455, A211457, A211458.

t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n], s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, {n, Length[s], s}]]]]; First/@Transpose[t][[3]]

A211457 Largest number b for which A181780(n) is a Fermat pseudoprime.

Original entry on oeis.org

11, 13, 18, 25, 23, 29, 25, 37, 31, 35, 29, 34, 37, 55, 57, 49, 47, 51, 49, 49, 43, 81, 59, 88, 61, 56, 89, 97, 73, 81, 91, 109, 69, 118, 83, 25, 68, 85, 81, 125, 109, 95, 131, 133, 97, 137, 145, 67, 94, 107, 139, 142, 150, 134, 165, 151, 113, 119, 121, 179

Offset: 1

T. D. Noe, Apr 13 2012

nonn

That is, the largest b for which b^(s-1) = 1 (mod s), where s is in A181780.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A181780, A211455, A211456, A211458.

t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n], s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, {n, Length[s], s}]]]]; Last/@Transpose[t][[3]]

A211458 The irregular triangle of all bases b for which A181780(n) is a Fermat pseudoprime.

Original entry on oeis.org

4, 11, 8, 13, 7, 18, 9, 25, 10, 23, 6, 29, 14, 25, 8, 17, 19, 26, 28, 37, 18, 19, 30, 31, 16, 35, 9, 29, 21, 34, 20, 37, 8, 55, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 25, 31, 37, 49, 22, 47, 11, 51, 26, 49, 45, 49, 34, 43, 4, 13, 16, 18, 21, 33

Offset: 1

T. D. Noe, Apr 13 2012

That is, all b for which b^(s-1) = 1 (mod s), where s is in A181780. Looking at the graph, it is apparent when a number such as 561 is a Carmichael number: there are 318 bases coprime to 561. These start at a(1937) and continue to a(2254).

			The irregular triangle begins
4, 11
8, 13
7, 18
9, 25
10, 23
6, 29
14, 25
8, 17, 19, 26, 28, 37
18, 19, 30, 31
16, 35

T. D. Noe, Rows n = 1..500 of an irregular triangle
Karsten Meyer, Tabelle Pseudoprimzahlen (15-4999)

Cf. A002997 (Carmichael numbers), A181780, A211455, A211456, A211457.

t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n], s = Select[Range[2, n-2], PowerMod[#, n-1, n] == 1 &]; If[s != {}, AppendTo[t, {n, Length[s], s}]]]]; Transpose[t][[3]]

A178958 Numbers n from A181780 that are not in A181781.

Original entry on oeis.org

15, 28, 35, 39, 51, 52, 55, 63, 66, 70, 75, 76, 87, 95, 99, 111, 112, 115, 119, 123, 124, 130, 135, 143, 147, 148, 154, 155, 159, 171, 172, 176, 183, 186, 187, 190, 195, 196, 203, 207, 208, 215, 219, 232, 235, 238, 244, 246, 255, 267, 268, 275, 276, 279, 280, 286, 287, 291, 292, 295, 299

Offset: 1

Karsten Meyer, Dec 31 2010

nonn

Numbers that are Fermat pseudoprimes to some base a (2<=a<=n-2) not Euler pseudoprimes to any base a (2<=a<=n-2).

			4^(15-1) == 1 (mod 15), but 4^((15-1)/2) == 4 (mod 15)

A181780

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);
}
esp(n)=
{ /* whether n is Euler pseudoprime to any base a where 2<=a<=n-2 */
    local(w);
    if ( n%2==0, return(0) );
    for (a=2,n-2,
        if ( gcd(a,n)!=1, next() );
        w = abs(component((Mod(a,n))^((n-1)/2),2));
        if ( (w==1) || (w==n-1), return(1) )
    );
    return(0);
}
for(n=3,300, if(isprime(n),next()); if( fsp(n) && (!esp(n)) , print1(n,", ") ); );

A039769 Composite integers k such that gcd(phi(k), k - 1) > 1.

Original entry on oeis.org

9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 81, 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

Offset: 1

Olivier Gérard

Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.
Equivalently, numbers n that are Fermat pseudoprimes to some base b, 1 < b < n.  A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n). Cf. A181780. - Geoffrey Critzer, Apr 04 2015
A071904, the odd composite numbers, is a subset of this sequence. - Peter Munn, May 15 2017
Lehmer's totient problem can be stated as finding a number in this sequence such that gcd(a(n) - 1, phi(a(n))) = phi(n). By the original definition of this sequence, such a number (if it exists) would not be in this sequence. - Alonso del Arte, Sep 07 2018, clarified Sep 14 2018

			phi(21) = 12 and gcd(12, 20) = 4 > 1, hence 21 is in the sequence.
phi(22) = 10 but gcd(10, 21) = 1, so 22 is not in the sequence.

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

Cf. A000010, A071904, A181780.

select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]);  # Robert Israel, Apr 07 2015

Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* Geoffrey Critzer, Apr 04 2015 *)

forcomposite(k=1, 1e3, if(gcd(eulerphi(k), k-1) > 1, print1(k, ", "))); \\ Altug Alkan, Sep 21 2018

Name clarified by Tom Edgar, Apr 05 2015

A105222 Smallest integer m > 1 such that m^(n-1) == 1 (mod n).

Original entry on oeis.org

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, 16, 9, 2, 55, 21, 57, 20, 59, 2, 61, 2, 63, 8, 65, 8, 25, 2, 69, 22, 11, 2, 73, 2, 75, 26

Offset: 1

Max Alekseyev, Apr 14 2005

Composite n are Fermat pseudoprimes to base a(n).

For n > 1; (5+(-1)^n)/2 <= a(n) <= n+(-1)^n. If n > 2 and a(n) > 2 then n is composite. - Thomas Ordowski, Dec 01 2013

			We have 2^(2-1) == 0, 3^(2-1) == 1 (mod 2), so a(2) = 3.

T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Wikipedia, Fermat pseudoprime

Cf. A007535, A181780, A239452.

Table[k = 2; While[PowerMod[k, n - 1, n] != 1, k++]; k, {n, 2, 100}] (* T. D. Noe, Dec 07 2013 *)

a(n) = {m = 2; while ((m^(n-1) % n) !=  lift(Mod(1, n)), m++); m; } \\ Michel Marcus, Dec 01 2013

a(n) = my(m=2); while(Mod(m, n)^(n-1)!=1, m++); m \\ Charles R Greathouse IV, Dec 01 2013

a(p) = 2 for odd prime p.

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Original entry on oeis.org

5, 7, 9, 8, 11, 13, 15, 4, 17, 19, 21, 8, 23, 25, 7, 27, 26, 9, 31, 33, 10, 35, 6, 37, 39, 14, 41, 43, 45, 8, 47, 49, 18, 51, 16, 9, 55, 21, 57, 20, 59, 61, 63, 8, 65, 8, 25, 69, 22, 11, 73, 75, 26, 45, 34, 79, 81, 80, 83, 85, 4, 87, 28, 89, 91, 3, 93, 32, 95

Offset: 1

Felix Fröhlich, Aug 16 2014

nonn

Felix Fröhlich, Table of n, a(n) for n = 1..8769 (all terms up to k=10^4)

Cf. A002808, A001567, A105222, A181780, A211455, A211456, A211457, A211458.

sbb[n_]:=Module[{b=2},While[PowerMod[b,n-1,n]!=1,b++];b]; sbb/@Select[ Range[ 100],CompositeQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 29 2018 *)

forcomposite(k=2, 1e2, for(b=2, 1e9, if(Mod(b, k)^(k-1)==1, print1(b, ", "); next({2}))); print1(">1e9, "))

a(n) = A105222(A002808(n)). - Michel Marcus, Aug 21 2014

A181781 Numbers n that are Euler pseudoprimes to some base b, 2 <= b <= n-2.

Original entry on oeis.org

21, 25, 33, 45, 49, 57, 65, 69, 77, 85, 91, 93, 105, 117, 121, 125, 129, 133, 141, 145, 153, 161, 165, 169, 175, 177, 185, 189, 201, 205, 209, 213, 217, 221, 225, 231, 237, 245, 247, 249, 253, 259, 261, 265, 273, 285, 289, 297, 301, 305, 309, 321, 325, 329, 333, 341, 343, 345

Offset: 1

Karsten Meyer, Nov 12 2010

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Karsten Meyer, Tabelle Pseudoprimzahlen (15-4999)
Karsten Meyer, Rexx program
Eric W. Weisstein, MathWorld: Euler Pseudoprime

Cf. A006970, A181780.

isEulPSP := proc(n,b) if isprime(n) then false; else m := modp(b &^ ((n-1)/2),n) ; if m= 1 or m = n-1 then true; else false; end if; end if;end proc:
isA181781 := proc(n) for b from 2 to n-2 do if isEulPSP(n,b) then return true; end if; end do: return false;end proc:
for n from 3 to 800 do if isA181781(n) then printf("%d,",n) ; end if; end do: # R. J. Mathar, May 30 2011

fQ[n_?PrimeQ, b_] = False; fQ[n_, b_] := Block[{p = PowerMod[b, (n - 1)/2, n]}, p == Mod[1, n] || p == Mod[-1, n]]; gQ[n_] := AnyTrue[Range[2, n - 2], fQ[n, #] &]; Select[2 Range[172] + 1, gQ] (* Michael De Vlieger, Sep 09 2015, after Jean-François Alcover at A006970, Version 10 *)

Definition corrected by Max Alekseyev, Nov 12 2010

Edited definition to be consistent with OEIS style. - N. J. A. Sloane, Nov 13 2010

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

cp's OEIS Frontend

A211455 The number of bases b for which A181780(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A211456 Smallest base b for which A181780(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A211457 Largest number b for which A181780(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A211458 The irregular triangle of all bases b for which A181780(n) is a Fermat pseudoprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A178958 Numbers n from A181780 that are not in A181781.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A039769 Composite integers k such that gcd(phi(k), k - 1) > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A105222 Smallest integer m > 1 such that m^(n-1) == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A242742 Let k be the n-th composite number: then a(n) is the smallest base b such that b^(k-1) == 1 (mod k).

Views

Author

Keywords

Links

Crossrefs