A060648 Number of cyclic subgroups of the group C_n X C_n (where C_n is the cyclic group of order n).

1, 4, 5, 10, 7, 20, 9, 22, 17, 28, 13, 50, 15, 36, 35, 46, 19, 68, 21, 70, 45, 52, 25, 110, 37, 60, 53, 90, 31, 140, 33, 94, 65, 76, 63, 170, 39, 84, 75, 154, 43, 180, 45, 130, 119, 100, 49, 230, 65, 148, 95, 150, 55, 212, 91, 198, 105, 124, 61, 350, 63, 132, 153, 190

Offset: 1

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001

Keywords

• nonn
• mult
• easy

Comments

The group U(n) of units modulo n acts on the direct product (Z_n)^k by multiplication. The number g(n,k) of orbits of U(n) acting on Z/(n)^k is g(n,k) = (1/phi(n))*Sum(gcd(n,a-1)^k) where the sum is over a in U(n) and phi(n) is the Euler totient function. A060648 gives g(n,2). - W. Edwin Clark, Jul 20 2001

a(n) is also the number of orbits of length n for the map TxT (Cartesion product) where T is a map with one orbit of each length. - Thomas Ward, Apr 08 2009

Examples

			The cycle index of C_4 X C_4 is (x(1)^4 + x(2)^2 + 2*x(4))^2 = x(1)^8 + 2*x(1)^4*x(2)^2 + 4*x(1)^4*x(4) + x(2)^4 + 4*x(2)^2*x(4) + 4*x(4)^2 and C_4 X C_4 has 1 element of order 1, 3 elements of order 2 and 12 elements of order 4. So a(4) = 1/phi(1) + 3/phi(2) + 12/phi(4) = 10, where phi = Euler totient function, cf. A000010. - _Vladeta Jovovic_, Jul 05 2001
For a(4) the pairs (e,d) are (1,4),(2,4),(4,4),(4,2),(4,1) with gcds 1,2,4,2,1 resp. giving 10 in total. - _Thomas Ward_, Apr 08 2009
		

Links

• Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000
• M. Hampejs, N. Holighaus, L. Toth and C. Wiesmeyr, On the subgroups of the group Z_m X Z_n, arXiv preprint arXiv:1211.1797 [math.GR], 2012-2014. - From _N. J. A. Sloane_, Jan 02 2013
• W. G. Nowak and L. Tóth, On the average number of subgroups of the group Z_m X Z_n, arXiv preprint arXiv:1307.1414 [math.NT], 2013.
• Apisit Pakapongpun and Thomas Ward, Functorial orbit counting, Journal of Integer Sequences, 12 (2009) Article 09.2.4.
• László Tóth, Menon's identity and arithmetical sums representing functions of several variables, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110, and arXiv:1103.5861, [math.NT], 2011.
• László Tóth, On the number of cyclic subgroups of a finite abelian group, arXiv: 1203.6201 [math.GR], 2012.
• László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013-2014.
• Index entries for sequences related to groups.

Crossrefs

Cf. A060724, A063379, A061503, A064969, A216620, A280184, A344219, A344302, A344303.

Programs

Maple

for n from 1 to 200 do:ans := 1:for i from 1 to nops(ifactors(n)[2]) do p := ifactors(n)[2][i][1]:e := ifactors(n)[2][i][2]:ans := ans*(p^(e+1)+p^e-2)/(p-1):od:printf(`%d,`,ans):od:

Mathematica

Table[ Plus @@ Map[ Times @@ (EulerPhi /@ #)/EulerPhi[ LCM @@ # ] &, Flatten[ Outer[ {##} &, Divisors[ i ], Divisors[ i ] ], 1 ] ], {i, 1, 100} ]
f[p_, e_] := (p^(e+1)+p^e-2)/(p-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 20 2020 *)

PARI

a(n) = sumdiv(n, d,  2^omega(d)*(n/d) ); \\ Joerg Arndt, Sep 16 2012

Sage

def A060648(n) :
    def dedekind_psi(n) : return n*mul(1+1/p for p in prime_divisors(n))
    return reduce(lambda x,y: x+y, [dedekind_psi(d) for d in divisors(n)])
[A060648(n) for n in (1..64)]  # Peter Luschny, Sep 10 2012

Formula

a(n) is multiplicative: if the canonical factorization of n is the product of p^e(p) over primes then a(n) = product a(p^e(p)). If n = p^e, p prime, a(n) = (p^(e+1)+p^e-2)/(p-1).

a(n) = Sum_{i|n, j|n} phi(i)*phi(j)/phi(lcm(i, j)). - Vladeta Jovovic, Jul 07 2001

a(n) = Sum_{i|n, j|n} phi(gcd(i, j)).

a(n) = Sum_{d|n} phi(n/d)*tau(d^2).

a(n) = sum(d|n, sigma(d)*moebius(n/d)^2 ). - Benoit Cloitre, Sep 08 2002

Inverse Euler transform of A156302. - Vladeta Jovovic, Feb 14 2009

Moebius transform of A060724. - Vladeta Jovovic, Apr 05 2009

Also a(n) = (1/n)*Sum_{d|n} sigma(d)^2*moebius(n/d). - Vladeta Jovovic, Mar 31 2009

Inverse Moebius transform of A001615. - Vladeta Jovovic, Apr 05 2009

From Thomas Ward, Apr 08 2009: (Start)

a(n) = Sum_{lcm(e,d)=n} gcd(e,d).

Dirichlet g.f.: zeta(s)^2*zeta(s-1)/zeta(2s). (End)

For the proofs of these formulas see the papers of L. Toth.

a(n) = Sum_{d|n} psi(d), where psi is Dedekind's psi function A001615. - Peter Luschny, Sep 10 2012

a(n) = Sum_{d|n} 2^omega(d)*(n/d). - Peter Luschny, Sep 15 2012

Sum_{k=1..n} a(k) ~ (5/4) * n^2. - Amiram Eldar, Oct 19 2022

a(n) = Sum_{k=1..n} tau(gcd(n,k)^2). - Ridouane Oudra, Apr 10 2023

a(n) = Sum_{d divides n} J_2(d)/phi(d) = Sum_{1 <= i, j <= n} 1/phi(n/gcd(i,j,n)), where the Jordan totient function J_2(n) = A007434(n). - Peter Bala, Jan 23 2024

Extensions

More terms and additional comments from Vladeta Jovovic, Jul 05 2001