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

Author

Valery A. Liskovets, Apr 15 2002

Keywords

• mult
• easy
• nonn

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

Crossrefs

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

Programs

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 *)

Scheme

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

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)