|
| |
|
|
A060648
|
|
Number of cyclic subgroups of the group C_n X C_n (where C_n is the cyclic group of order n).
|
|
37
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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
|
|
|
LINKS
|
|
|
|
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
Also a(n) = (1/n)*Sum_{d|n} sigma(d)^2*moebius(n/d). - Vladeta Jovovic, Mar 31 2009
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.
Sum_{k=1..n} a(k) ~ (5/4) * n^2. - Amiram Eldar, Oct 19 2022
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
|
|
|
EXAMPLE
|
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
|
|
|
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 *)
|
|
|
PROG
|
(Sage)
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)])
(PARI) a(n) = sumdiv(n, d, 2^omega(d)*(n/d) ); \\ Joerg Arndt, Sep 16 2012
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,mult,easy
|
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 04 2001
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
