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
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.
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
Comments