A069739 Size of the key space for isomorphism verification of circulant graphs of order n.

1, 1, 1, 2, 1, 1, 1, 5, 2, 1, 1, 2, 1, 1, 1, 14, 1, 2, 1, 2, 1, 1, 1, 5, 2, 1, 5, 2, 1, 1, 1, 42, 1, 1, 1, 4, 1, 1, 1, 5, 1, 1, 1, 2, 2, 1, 1, 14, 2, 2, 1, 2, 1, 5, 1, 5, 1, 1, 1, 2, 1, 1, 2, 132, 1, 1, 1, 2, 1, 1, 1, 10, 1, 1, 2, 2, 1, 1, 1, 14, 14, 1, 1, 2, 1, 1, 1, 5, 1, 2

Offset

1,4

Comments

Multiplicative with a(p^m) = Catalan(m) (A000108). Coincides with A066060 up to n=63 except for n=32.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. (3) 88 (2004), no. 1, 1-41.

Index entries for sequences computed from exponents in factorization of n

Formula

a(n) = prod_p Catalan(m_p) where n=prod_p p^(m_p), p|n prime.

From Antti Karttunen, May 28-29 2017: (Start)

a(1) = 1; for n > 1, a(n) = A000108(A067029(n)) * a(A028234(n)).

a(n) = A246596(A156552(n)). (End)

Maple

A000108 := proc(n) binomial(2*n, n)/(n+1) ; end proc:
A069739 := proc(n) local ifa; if n = 1 then 1; else ifa := ifactors(n)[2] ; mul( A000108(op(2, f)), f=ifa) ; end if; end proc:
seq(A069739(n), n=1..90) ; # R. J. Mathar, Feb 08 2011

Mathematica

Table[Times @@ Map[CatalanNumber, FactorInteger[n][[All, -1]]], {n, 90}] (* Michael De Vlieger, May 28 2017 *)

Prog

(Scheme) (define (A069739 n) (if (= 1 n) n (* (A000108 (A067029 n)) (A069739 (A028234 n))))) ;; Antti Karttunen, May 28 2017

Crossrefs

Cf. A000108, A066060, A028234, A067029, A156552, A246596.

Sequence in context: A351861 A343233 A155586 * A066060 A008550 A064094

Adjacent sequences: A069736 A069737 A069738 * A069740 A069741 A069742

Keyword

mult,easy,nonn

Author

Valery A. Liskovets, Apr 15 2002

Status

approved