A003277 -id:A003277 - cp's OEIS frontend

A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 7, 5, 1, 2, 1, 3, 5, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 5, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 7, 3, 5, 1, 2, 1, 2, 3

Offset: 1

Labos Elemer, Apr 07 2003

nonn

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

Cf. A000010, A003277, A006530, A009195, A070003.

Cf. also A082062, A082063, A082064, A082065, A082066, A082067.

gcpd := proc(a,b) local g ,d ; g := 1 ; for d in numtheory[divisors](a) intersect numtheory[divisors](b) do if isprime(d) then g := max(g,d) ; end if; end do: g ; end proc:
A082061 := proc(n) gcpd( numtheory[phi](n), n) ; end proc: # R. J. Mathar, Jul 09 2011

(* factors/exponent SET *) ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := x; f2[x_] := EulerPhi[x]; Table[Max[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Max@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
a(n)=gpf(gcd(eulerphi(n),n)) \\ Charles R Greathouse IV, Feb 19 2013

a(n) = A006530(A009195(n)). - Antti Karttunen, Nov 03 2017
From Amiram Eldar, Dec 06 2024: (Start)
a(n) <= A006530(n), with equality if and only if n is in A070003.
a(n) = 1 if and only if n is a cyclic number (A003277). (End)

Changed "was found" to "exists" in definition. - N. J. A. Sloane, Jan 29 2022

A235863 Exponent of the multiplicative group G_n:={x+iy: x^2+y^2==1 (mod n); 0 <= x,y < n} where i=sqrt(-1).

Original entry on oeis.org

1, 2, 4, 4, 4, 4, 8, 4, 12, 4, 12, 4, 12, 8, 4, 4, 16, 12, 20, 4, 8, 12, 24, 4, 20, 12, 36, 8, 28, 4, 32, 8, 12, 16, 8, 12, 36, 20, 12, 4, 40, 8, 44, 12, 12, 24, 48, 4, 56, 20, 16, 12, 52, 36, 12, 8, 20, 28, 60, 4, 60, 32, 24, 16, 12, 12, 68, 16, 24, 8, 72

Offset: 1

José María Grau Ribas, Jan 16 2014

nonn

From Jianing Song, Nov 05 2019: (Start)
Exponent of the group G is the least e > 0 such that x^e = 1 for every x in G, where 1 is the identity element.
Also the exponent of O(2,Z_n) or SO(2,Z_n). O(2,Z_n) is the group of 2 X 2 matrices A over Z_n such that A*A^T = E = [1,0;0,1]; SO(2,Z_n) is the group of 2 X 2 matrices A over Z_n such that A*A^T = E = [1,0;0,1] and det(A) = 1. Note that G_n is isomorphic to SO(2,Z_n) by the mapping x+yi <-> [x,y;-y,x]. See A060698 for the group structure of SO(2,Z_n) and A182039 for the group structure of O(2,Z_n). (End)

Andrew Howroyd, Table of n, a(n) for n = 1..10000
José María Grau, A. M. Oller-Marcén, Manuel Rodriguez and Daniel Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.
José María Grau, A. M. Oller-Marcén, Manuel Rodriguez and Daniel Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, Czechoslovak Mathematical Journal 65(140), (2015) pp. 969-982.

                                   (Z/nZ)*    ------    G_n
Order:                             A000010    ------  A060968.
Exponent:                          A002322    ------  this sequence.
                                     n-1      ------  A201629.
Carmichael/G-Carmichael numbers:   A002997    ------  A235865.
Lehmer /G-Lehmer numbers:          unknown    ------  A235864.
Cyclic/G-cyclic numbers:           A003277    ------  A235866.
n such that the group is cyclic:   A033948    ------  A235868.
Cf. A060698, A182039.

fa=FactorInteger; lam[1]=1;lam[p_, s_] := Which[Mod[p, 4] == 3, p ^ (s - 1 ) (p + 1) , Mod[p, 4] == 1, p ^ (s - 1 ) (p - 1)  , s ≥ 5, 2 ^ (s - 2 ), s > 1, 4, s == 1, 2];lam[n_] := {aux = 1; Do[aux = LCM[aux, lam[fa[n][[i, 1]], fa[n][[i, 2]]]], {i, 1, Length[fa[n]]}]; aux}[[1]] ; Array[lam, 100]

a(n)={my(f=factor(n)); lcm(vector(#f~, i, my([p,e]=f[i,]); if(p==2, 2^max(e-2, min(e,2)), p^(e-1)*if(p%4==1, p-1, p+1))))} \\ Andrew Howroyd, Aug 06 2018

a(2) = 2, a(4) = a(8) = a(16) = 4, a(2^e) = 2^(e-2) for e >= 5; a(p^e) = (p-1)*p^(e-1) if p == 1 (mod 4) and (p+1)*p^(e-1) if p == 1 (mod 4). - Jianing Song, Nov 05 2019

If gcd(n,m)=1 then a(nm) = lcm(a(n), a(m)).

A187731 Numbers n such that rad(phi(n)) divides n-1.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 97, 101, 103, 107, 109, 113, 127, 131, 133, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 247, 251, 255, 257, 259

Offset: 1

José María Grau Ribas, Mar 13 2011

nonn

Subsequence of A003277 (cyclic numbers).
Let L(x) = exp(log x log log log x/log log x). McNew shows that there are at most x/L(x)^(1+o(1)) members of this sequence up to x. - Charles R Greathouse IV, Oct 08 2012
Contains all primes A000040 and all Carmichael numbers A002997. - Jeppe Stig Nielsen, Jul 27 2020

			15 is in the sequence because phi(15)=8, rad(8)=2 and 2 divides 15-1.

Amiram Eldar, Table of n, a(n) for n = 1..10000
José María Grau and Antonio M. Oller-Marcén, On k-Lehmer numbers, Integers, 12(2012), #A37
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions (2012)

Cf. A000010, A002997 (Carmichael numbers), A003277 (cyclic numbers), A007947, A080400.

rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[Range[1000], Mod[#-1,rad[EulerPhi[#]]]==0&]

rad(n)=n=factor(n);prod(i=1,#n[,1],n[i,1]);
for(n=1,1e4,if((n-1)%rad(eulerphi(n))==0,print1(n", "))) \\ Charles R Greathouse IV, Jul 04 2011

is(n)=my(p=eulerphi(n), g=n); n--; while((g=gcd(p, g))>1, p/=g); p==1 && n \\ Charles R Greathouse IV, Mar 03 2014

A238574 k-Lehmer numbers: composite integers n such that phi(n) | (n-1)^k.

Original entry on oeis.org

15, 51, 85, 91, 133, 247, 255, 259, 435, 451, 481, 511, 561, 595, 679, 703, 763, 771, 949, 1105, 1111, 1141, 1261, 1285, 1351, 1387, 1417, 1615, 1695, 1729, 1843, 1891, 2047, 2071, 2091, 2119, 2431, 2465, 2509, 2701, 2761, 2821, 2955, 3031, 3097, 3145, 3277

Offset: 1

José María Grau Ribas, Mar 01 2014

nonn

Composite numbers in A187731.

J. M. Grau and A. M. Oller-Marcén showed that all terms of this sequence are terms of A003277 (cyclic numbers) and this sequence contains all terms of A002997 (Carmichael numbers). - Tomohiro Yamada, Sep 28 2020

			2^3*3^2 = 72 = phi(91) divides (91-1)^3 = (2*3^2*5)^3 implies 91 is a 3-Lehmer number.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
J. M. Grau and A. M. Oller-Marcén, On k-Lehmer numbers, Integers, 12(2012), #A37.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80.
Nathan McNew, Radically weakening the Lehmer and Carmichael conditions, arXiv:1210.2001 [math.NT], 2012; International Journal of Number Theory 9 (2013), 1215-1224.
Nathan McNew, Multiplicative problems in combinatorial number theory, Thesis, 2015.
Nathan McNew and Thomas Wright, Infinitude of k-Lehmer numbers which are not Carmichael, Int. J. Number Theory V.12(7), pp. 1863-1869, (2016).
Giovanni Resta, k-Lehmer numbers.

Cf. A187731 (numbers n such that rad(phi(n)) divides n-1).
Cf. A173703 (2-Lehmer numbers; i.e., phi(n) divides (n-1)^2).
Cf. A234936 (smallest composite n-Lehmer number which is not an (n-1)-Lehmer number).
Cf. A207080 (minimum Carmichael number which is not an n-Lehmer number).
Cf. A234958 (number of k-Lehmer numbers up to 10^n).
Cf. A238575 (k-Lehmer numbers with two prime factors).
Cf. A002997, A003277.

rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[1+Range[1000], !PrimeQ[#]&&Mod[#-1, rad[EulerPhi[#]]]==0&]

is(n)=my(p=eulerphi(n),g=n); if(isprime(n),return(0),n--); while((g=gcd(p,g))>1, p/=g); p==1 && n \\ Charles R Greathouse IV, Mar 03 2014

A331175 Number of values of k, 1 <= k <= n, with A109395(k) = A109395(n), where A109395(n) = n/gcd(n, phi(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 3, 3, 2, 1, 4, 1, 2, 1, 4, 1, 5, 1, 3, 3, 2, 1, 6, 4, 2, 7, 4, 1, 2, 1, 5, 1, 2, 1, 8, 1, 2, 3, 5, 1, 5, 1, 3, 3, 2, 1, 9, 6, 6, 1, 4, 1, 10, 4, 7, 3, 2, 1, 4, 1, 2, 8, 6, 1, 2, 1, 3, 1, 2, 1, 11, 1, 2, 5, 4, 1, 5, 1, 7, 12, 2, 1, 9, 1, 2, 1, 5, 1, 6, 1, 3, 3, 2, 1, 13, 1, 10, 3, 8, 1, 2, 1, 6, 3

Offset: 1

Antti Karttunen, Jan 11 2020

nonn

Ordinal transform of A109395.

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

Cf. A000010, A003277, A009195, A109395.

Cf. also A081373, A330746, A331177.

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A109395(n) = n/gcd(n, eulerphi(n));
v331175 = ordinal_transform(vector(up_to, n, A109395(n)));
A331175(n) = v331175[n];

For n >= 1, a(2^n) = n, a(A003277(n)) = 1.

A373648 Integers k such that there are i groups of order k+i up to isomorphism, for i=1,2.

Original entry on oeis.org

2, 4, 12, 32, 36, 60, 72, 84, 132, 140, 144, 156, 176, 192, 212, 216, 276, 312, 344, 392, 396, 420, 444, 456, 480, 500, 536, 540, 552, 560, 564, 612, 660, 672, 696, 704, 716, 732, 744, 756, 792, 816, 864, 876, 884, 912, 932, 956, 972, 996, 1040, 1092, 1140, 1152, 1172, 1200

Offset: 1

Robin Jones, Jun 12 2024

nonn

All the terms are even. - Robin Jones, Apr 18 2025

			2 is a term since there is 1 group of order 3 up to isomorphism, 2 of order 4.

Robin Jones, Table of n, a(n) for n = 1..500

Equals A296023 - 1.
Cf. A373649 (i=1,2,3), A373650 (i=1,2,3,4), A381335 (i=1,2,3,4,5).
Subsequence of A003277 - 1.

A034383 Number of labeled groups.

Original entry on oeis.org

1, 2, 3, 16, 30, 480, 840, 22080, 68040, 1088640, 3991680, 259459200, 518918400, 16605388800, 163459296000, 10353459916800, 22230464256000, 1867358997504000, 6758061133824000, 648773868847104000, 5474029518397440000, 122618261212102656000

Offset: 1

Christian G. Bower

nonn

From Jianing Song, Mar 02 2024: (Start)
In other words, number of ways to define a group structure on a set of n elements. Note that for a group G, a group structure on the set G is given by mapping (x,y) to sigma^(-1)(sigma(x)*sigma(y)), where sigma is a bijection on the set G; sigma and sigma' give the same structure if and only if sigma' is the composition of a group automorphism of G and sigma.
By definition, a(n) = A034381(n) if n in A003277, otherwise a(n) > A034381(n). The indices of records of a(n)/A034381(n) among the known terms are 1, 4, 8, 16, 24, 32, 48, 64, 96, 128, 192, with a(192)/A034381(192) = 122774329/1640520 ~ 74.8.
Also by definition, a(n) >= A000001(n)*n!/A059773(n). If the conjecture A059773(2^r) = A002884(r) is true, then A059773(2^r) <= 2^(r^2), while A000001(2^r) >= 2^((2/27)*r^2*(r-6)) (see the Math Stack Exchange link below), so a(2^r)/A034381(2^r) tends to infinity quickly as r tends to infinity.
The sequence is strictly increasing for the first 256 terms (a(256) > A034381(256) > A034381(255) = a(255) since 255 is in A003277). On the other hand, assuming that A059773(2^r) = A002884(r), then a(2^20)/(2^20)! >= A000001(2^20)/A002884(20) > 99798.4, while a(2^20+1)/(2^20)! = A034381(2^20+1)/(2^20)! = (2^20+1)/phi(2^20+1) since 2^20+1 = 17*61681 is in A003277, so we would have a(2^20) > a(2^20+1). It is conjectured a(2^r) > a(2^r+1) for all sufficiently large r. (End)

Stephen A. Silver, Table of n, a(n) for n = 1..255
H. U. Besche, The Small Groups library
Math Stack Exchange, Known bounds for the number of groups of a given order.
Index entries for sequences related to groups

Cf. A000001, A034381, A034382, A058157, A058163.

A034383 := function(n) local fn, sum, k; fn := Factorial(n); sum := 0; for k in [1 .. NrSmallGroups(n)] do sum := sum + fn / Size(AutomorphismGroup(SmallGroup(n,k))); od; return sum; end; # Stephen A. Silver, Feb 10 2013

a(n) = n * A058163(n).

a(n) = Sum n!/|Aut(G)|, where the sum is taken over the different products G of cyclic groups with |G| = n.

More terms from Stephen A. Silver, Feb 10 2013

A001914 Cyclic numbers: 10 is a quadratic residue modulo p and class of mantissa is 2.

Original entry on oeis.org

2, 13, 31, 43, 67, 71, 83, 89, 107, 151, 157, 163, 191, 197, 199, 227, 283, 293, 307, 311, 347, 359, 373, 401, 409, 431, 439, 443, 467, 479, 523, 557, 563, 569, 587, 599, 601, 631, 653, 677, 683, 719, 761, 787, 827, 839, 877, 881, 883, 911, 919, 929, 947, 991

Offset: 1

N. J. A. Sloane

nonn

Also, apart from first term 2, primes p for which the repunit (A002275) R((p-1)/2)=(10^((p-1)/2)-1)/9 is the smallest repunit divisible by p. Primes for which A000040(n) = 2*A071126(n) + 1. - Hugo Pfoertner, Mar 18 2003, Sep 18 2018

			The repunit R(6)=111111 is the smallest repunit divisible by the prime a(2)=13=2*6+1.

Albert H. Beiler, Recreations in the Theory of Numbers, 2nd ed. New York: Dover, 1966. Pages 65, 309.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 61.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hugo Pfoertner, Table of n, a(n) for n = 1..1180

Cf. A003277 for another sequence of cyclic numbers.

Cf. A000040, A002275, A071126.

R(n)=(10^n-1)/9;
print1(2,", "); forprime(p=3, 1000, m=0; for(q=3, (p-1)/2-1, if(R(q)%p==0, m=1; break));if(m==0&&R((p-1)/2)%p==0, print1(p,", "))) \\ Hugo Pfoertner, Sep 18 2018

More terms from Enoch Haga

A003431 Number of isomorphism classes of connected irreducible posets with n labeled points.

Original entry on oeis.org

1, 1, 0, 0, 1, 12, 104, 956, 10037, 126578, 1971005, 38569954, 958347642, 30400603560, 1234260982770, 64187360439352, 4275470549123119

Offset: 0

N. J. A. Sloane and Richard Stanley

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. R. Finch, Series-parallel networks
S. R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295-299.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for sequences related to posets

Cf. A003430, A046906.

More terms from Richard Stanley, Jun 19 2003
2 more terms from Vladeta Jovovic, Feb 17 2008
Title clarified by Geoffrey Critzer, Jul 08 2022
a(0) changed to 1 by Geoffrey Critzer, Jul 10 2022

A235866 G-cyclic numbers: numbers n such that gcd(n,A060968(n))=1.

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 15, 17, 19, 21, 23, 29, 31, 35, 37, 41, 43, 47, 51, 53, 55, 57, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 87, 89, 91, 93, 97, 101, 103, 105, 107, 109, 113, 115, 119, 123, 127, 129, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 159, 161

Offset: 1

José María Grau Ribas, Jan 19 2014

nonn

From Robert Israel, May 01 2020: (Start)
All terms are odd and squarefree.
Contains all odd primes.
If n is a member, then so are all divisors of n.
(End)

Robert Israel, Table of n, a(n) for n = 1..10000
Jose María Grau, A. M. Oller-Marcen, Manuel Rodriguez and D. Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.

Cf. A060968, A003277.

g:= proc(p,e) if p=2 or e > 1 then 0
  elif p mod 4 = 1 then p-1 else p+1 fi
end proc:
h:= proc(n) mul(g(t[1],t[2]),t=ifactors(n)[2]) end proc:
select(n -> igcd(n,h(n))=1, [seq(i,i=1..2000,2)]); # Robert Israel, May 01 2020

fa=FactorInteger; phi[1]=1;phi[p_, s_] := Which[Mod[p, 4] == 1, p^(s-1)*(p-1), Mod[p, 4]==3, p^(s-1)*(p+1), s==1, 2, True, 2^(s+1)]; phi[1]=1; phi[n_] := Product[phi[fa[n][[i, 1]], fa[n][[i, 2]]], {i, Length[fa[n]]}]; Select[Range[1000], GCD[phi[#], #] == 1 &]

genit(maxx)={arr=List(); for(ptr=1, maxx, if(gcd(ptr,A060968(ptr))==1, listput(arr,ptr))); arr}
\\******** following code taken from A060968
A060968(n)={my(f=factor(n)[,1]); q=n*prod(i=if(n%2,1,2),#f,if(f[i]%4==1,1-1/f[i],1+1/f[i]))*if(n%4,1,2);return(q);} \\ Bill McEachen, Jul 16 2021

cp's OEIS Frontend

A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A235863 Exponent of the multiplicative group G_n:={x+iy: x^2+y^2==1 (mod n); 0 <= x,y < n} where i=sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A187731 Numbers n such that rad(phi(n)) divides n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A238574 k-Lehmer numbers: composite integers n such that phi(n) | (n-1)^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A331175 Number of values of k, 1 <= k <= n, with A109395(k) = A109395(n), where A109395(n) = n/gcd(n, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A373648 Integers k such that there are i groups of order k+i up to isomorphism, for i=1,2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A034383 Number of labeled groups.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Formula

Extensions

A001914 Cyclic numbers: 10 is a quadratic residue modulo p and class of mantissa is 2.

Views

Author

Keywords