login
Number (up to isomorphism) of groups of order 2n that have Z/nZ as a subgroup (that is, that have an element of order n).
4

%I #82 Sep 11 2022 18:26:24

%S 1,2,2,4,2,4,2,6,2,4,2,8,2,4,4,6,2,4,2,8,4,4,2,12,2,4,2,8,2,8,2,6,4,4,

%T 4,8,2,4,4,12,2,8,2,8,4,4,2,12,2,4,4,8,2,4,4,12,4,4,2,16,2,4,4,6,4,8,

%U 2,8,4,8,2,12,2,4,4,8,4,8,2,12,2,4,2,16,4

%N Number (up to isomorphism) of groups of order 2n that have Z/nZ as a subgroup (that is, that have an element of order n).

%C This sequence is related to A060594: in fact, for every square root of unity modulo n, there are either one or two such groups of order 2n.

%C For n >= 3, a(n) is also the number of equivalence classes of automorphisms of order 2 (involutions) of the dihedral group D_n (see the reference below). - _Tom Edgar_, Jul 03 2013

%H Charles R Greathouse IV, <a href="/A147848/b147848.txt">Table of n, a(n) for n = 1..10000</a>

%H K. K. A. Cunningham, Tom Edgar, A. G. Helminck, B. F. Jones, H. Oh, R. Schwell and J. F. Vasquez, <a href="http://dx.doi.org/10.1285/i15900932v34n2p23">On the Structure of Involutions and Symmetric Spaces of Dihedral Groups</a>, Note di Mat., Volume 34, No. 2, 2014.

%H Tom Edgar, <a href="https://community.plu.edu/~edgartj/dihedral.pdf">Generalized Symmetric Spaces of Dihedral Groups</a>, talk slides, (2012).

%F a(2) = 2, a(2^2) = 4, a(2^k) = 6 for k >= 3.

%F a(p^k) = 2 for any odd prime number p and k >= 1.

%F For other values of n, you can find a(n) by using the fact that the sequence is multiplicative.

%F Dirichlet g.f.: zeta^2(s)*(1+2^s+2^(1-s)-4^(1-s)+6*4^(-s)) / ( zeta(2*s)*(1+2^s) ). - _R. J. Mathar_, Jun 01 2011

%F Sum_{k=1..n} a(k) ~ (9*n/Pi^2) * (log(n) - 1 + 2*gamma - 2*log(2)/3 - 12*Zeta'(2) / Pi^2), where gamma is the Euler-Mascheroni constant A001620. - _Vaclav Kotesovec_, Feb 07 2019

%F From _Mats Granvik_, Mar 03 2019: (Start)

%F a(n) = Sum_{m=1..n} Sum_{k=1..n} (k divides n)*(n/k divides m)*(k divides m + 2).

%F a(n) = Sum_{k=1..n} (k divides n)*Sum_{j=1..2} (gcd(k, n/k) = j)*j. (End)

%e Two such groups that always exist are the cyclic group Z/(2n)Z and the dihedral group Dih_n. If n is prime, these are the only such groups, so a(p)=2 when p is prime.

%e For even values of n, we also have the direct product Z/nZ x Z/2Z and the dicyclic group Dic_n. If n = 2p with p prime, there are no other groups, so a(2*p)=4 when p is prime.

%e There exist five groups (up to isomorphism) of order 2*4 = 8. Four of them have Z/4Z as a subgroup, the two abelian groups: Z/8Z and Z/4Z x Z/2Z, also the two nonabelian groups: the Dihedral group Dih_4 and the Quaternion group or Hamiltonian group: Q_8 = H_8 = Dic_2. So, a(4) = 4. The only group which does not have Z/4Z as a subgroup is the abelian group Z/2Z x Z/2Z x Z/2Z = (Z/2Z)^3. - _Bernard Schott_, Mar 03 2019

%t a[1] = 1; a[2] = 2; a[4] = 4; a[n_] := a[n] = (f = FactorInteger[n]; np = Length[f]; Which[ np == 1 && f[[1, 1]] == 2 && f[[1, 2]] >= 3, 6, np == 1 && PrimeQ[f[[1, 1]]] && f[[1, 2]] >= 1, 2, np > 1 && f[[1, 1]] != 2, 2^np, np > 1 && f[[1]] == {2, 1}, 2^np, np > 1 && f[[1]] == {2, 2}, 2^(np+1), np > 1 && f[[1, 1]] == 2 && f[[1, 2]] > 1, 3*2^np, True, 0]); Table[a[n], {n, 1, 60}](* _Jean-François Alcover_, Nov 22 2011 *)

%t a[n_] := Sum[Sum[If[Mod[n, k] == 0, If[Mod[m, n/k] == 0, 1, 0], 0]*If[Mod[m + 2, k] == 0, 1, 0], {k, 1, n}], {m, 1, n}]; a /@Range[85] (* Dirichlet convolution, _Mats Granvik_, Mar 03 2019 *)

%t a[n_] := Sum[If[Mod[n, k] == 0, Sum[If[GCD[k, n/k] == j, j, 0], {j, 2}],

%t 0], {k, n}]; a /@ Range[85] (* GCD sum, _Mats Granvik_, Mar 03 2019 *)

%t a[n_] := Sum[j*Count[Divisors[n], d_ /; GCD[d, n/d] == j], {j, 2}];

%t a/@Range[85] (* After Jean-François Alcover in A034444. - _Mats Granvik_, Mar 03 2019 *)

%t f[2, e_] := Which[e == 1, 2, e == 2, 4, e >= 3, 6]; f[p_, e_] := 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Sep 17 2020 *)

%o (PARI) a(n)=my(k=valuation(n,2));max(2*min(k,3),1)<<omega(n>>k) \\ _Charles R Greathouse IV_, Nov 22 2011

%Y Cf. A001620, A060594.

%K easy,nice,nonn,mult

%O 1,2

%A Ilia Smilga (ilia.smilga(AT)ens.fr), Nov 15 2008

%E Extended comments, references and confirmed "mult" keyword. - Ilia Smilga (ilia.smilga(AT)ens.fr), Nov 17 2008