login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060648 Number of cyclic subgroups of the group C_n X C_n (where C_n is the cyclic group of order n). 18
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). - 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 (t.ward(AT)uea.ac.uk), 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, 2012. - 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, 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.

László Tóth, On the number of cyclic subgroups of a finite abelian group, arXiv: 1203.6201 (2012).

L. Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053, 2013

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

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

Also 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 (t.ward(AT)uea.ac.uk), 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 formulae 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

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 (t.ward(AT)uea.ac.uk), 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} ]

PROG

(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

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

CROSSREFS

Cf. A060724, A063379, A061503, A216620.

Sequence in context: A009778 A215754 A226486 * A092961 A177711 A115945

Adjacent sequences:  A060645 A060646 A060647 * A060649 A060650 A060651

KEYWORD

nonn,mult

AUTHOR

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

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 31 03:48 EDT 2014. Contains 248845 sequences.