|
%I #90 Jan 24 2024 08:02:52
%S 1,4,5,10,7,20,9,22,17,28,13,50,15,36,35,46,19,68,21,70,45,52,25,110,
%T 37,60,53,90,31,140,33,94,65,76,63,170,39,84,75,154,43,180,45,130,119,
%U 100,49,230,65,148,95,150,55,212,91,198,105,124,61,350,63,132,153,190
%N Number of cyclic subgroups of the group C_n X C_n (where C_n is the cyclic group of order n).
%C 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
%C 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
%H Enrique Pérez Herrero, <a href="/A060648/b060648.txt">Table of n, a(n) for n = 1..5000</a>
%H M. Hampejs, N. Holighaus, L. Toth and C. Wiesmeyr, <a href="http://arxiv.org/abs/1211.1797">On the subgroups of the group Z_m X Z_n</a>, arXiv preprint arXiv:1211.1797 [math.GR], 2012-2014. - From _N. J. A. Sloane_, Jan 02 2013
%H W. G. Nowak and L. Tóth, <a href="https://arxiv.org/abs/1307.1414">On the average number of subgroups of the group Z_m X Z_n</a>, arXiv preprint arXiv:1307.1414 [math.NT], 2013.
%H Apisit Pakapongpun and Thomas Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Ward/ward17.html">Functorial orbit counting</a>, Journal of Integer Sequences, 12 (2009) Article 09.2.4.
%H László Tóth, <a href="http://www.seminariomatematico.polito.it/rendiconti/69-1/97.pdf">Menon's identity and arithmetical sums representing functions of several variables</a>, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97-110, and <a href="http://arxiv.org/abs/1103.5861">arXiv:1103.5861</a>, [math.NT], 2011.
%H László Tóth, <a href="http://arxiv.org/abs/1203.6201">On the number of cyclic subgroups of a finite abelian group</a>, arXiv: 1203.6201 [math.GR], 2012.
%H László Tóth, <a href="http://arxiv.org/abs/1310.7053">Multiplicative arithmetic functions of several variables: a survey</a>, arXiv preprint arXiv:1310.7053 [math.NT], 2013-2014.
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>.
%F 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).
%F a(n) = Sum_{i|n, j|n} phi(i)*phi(j)/phi(lcm(i, j)). - _Vladeta Jovovic_, Jul 07 2001
%F a(n) = Sum_{i|n, j|n} phi(gcd(i, j)).
%F a(n) = Sum_{d|n} phi(n/d)*tau(d^2).
%F a(n) = sum(d|n, sigma(d)*moebius(n/d)^2 ). - _Benoit Cloitre_, Sep 08 2002
%F Inverse Euler transform of A156302. - _Vladeta Jovovic_, Feb 14 2009
%F Moebius transform of A060724. - _Vladeta Jovovic_, Apr 05 2009
%F Also a(n) = (1/n)*Sum_{d|n} sigma(d)^2*moebius(n/d). - _Vladeta Jovovic_, Mar 31 2009
%F Inverse Moebius transform of A001615. - _Vladeta Jovovic_, Apr 05 2009
%F From _Thomas Ward_, Apr 08 2009: (Start)
%F a(n) = Sum_{lcm(e,d)=n} gcd(e,d).
%F Dirichlet g.f.: zeta(s)^2*zeta(s-1)/zeta(2s). (End)
%F For the proofs of these formulas see the papers of L. Toth.
%F a(n) = Sum_{d|n} psi(d), where psi is Dedekind's psi function A001615. - _Peter Luschny_, Sep 10 2012
%F a(n) = Sum_{d|n} 2^omega(d)*(n/d). - _Peter Luschny_, Sep 15 2012
%F Sum_{k=1..n} a(k) ~ (5/4) * n^2. - _Amiram Eldar_, Oct 19 2022
%F a(n) = Sum_{k=1..n} tau(gcd(n,k)^2). - _Ridouane Oudra_, Apr 10 2023
%F 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
%e 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
%e 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
%p 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:
%t Table[ Plus @@ Map[ Times @@ (EulerPhi /@ #)/EulerPhi[ LCM @@ # ] &, Flatten[ Outer[ {##} &, Divisors[ i ], Divisors[ i ] ], 1 ] ], {i, 1, 100} ]
%t 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 *)
%o (Sage)
%o def A060648(n) :
%o def dedekind_psi(n) : return n*mul(1+1/p for p in prime_divisors(n))
%o return reduce(lambda x,y: x+y, [dedekind_psi(d) for d in divisors(n)])
%o [A060648(n) for n in (1..64)] # _Peter Luschny_, Sep 10 2012
%o (PARI) a(n) = sumdiv(n, d, 2^omega(d)*(n/d) ); \\ _Joerg Arndt_, Sep 16 2012
%Y Cf. A060724, A063379, A061503, A064969, A216620, A280184, A344219, A344302, A344303.
%K nonn,mult,easy
%O 1,2
%A Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001
%E More terms and additional comments from _Vladeta Jovovic_, Jul 05 2001
|
