A032170 "CHK" (necklace, identity, unlabeled) transform of 1, 2, 3, 4, ...

1, 2, 5, 10, 24, 50, 120, 270, 640, 1500, 3600, 8610, 20880, 50700, 124024, 304290, 750120, 1854400, 4600200, 11440548, 28527320, 71289000, 178526880, 447910470, 1125750120, 2833885800, 7144449920, 18036373140, 45591631800, 115381697740, 292329067800

Offset: 1

Author

Christian G. Bower

Keywords

• nonn

Comments

Apparently, for n > 2, the same as A072337. - Ralf Stephan, Feb 01 2004

a(n) is the number of prime period-n periodic orbits of Arnold's cat map. - Bruce Boghosian, Apr 26 2009

From Petros Hadjicostas, Nov 17 2017: (Start)

A first proof of the g.f., given below, can be obtained using the first of Vladeta Jovovic's formulae. If b(n) = A004146(n), then B(x) = Sum_{n >= 1} b(n)*x^n = x*(1 + x)/((1 - x)*(1 - 3*x + x^2)) (see the documentation for sequence A004146). From Jovovich's first formula, A(x) = Sum_{n >= 1} a(n)*x^n = Sum_{n >= 1} (1/n)*Sum_{d | n} mu(d)*b(n/d)*x^n. Letting m = n/d, we get A(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{m >= 1} b(m)*(x^d)^m/m = Sum_{d >= 1} (mu(d)/d)*f(x^d), where f(y) = Sum_{m >= 1} b(m)*y^m/m = int(B(w)/w, w = 0..y) = int((1 + w)/((1 - w)*(1 - 3*w + w^2)), w = 0..y) = log((1 - y)^2/(1 - 3*y + y^2)) for |y| < (3 - sqrt(5))/2.

A second proof of the g.f. can be obtained using C. G. Bower's definition of the CHK transform of a sequence (e(n): n>=1) with g.f. E(x) (see the links below). If (c_k(n): n >= 1) = CHK_k(e(n): n >= 1), then (c_k(n): n >= 1) = (1/k)*(MOEBIUS*AIK)k (e_n: n >= 1) = (1/k)*Sum{d | gcd(n,k)} mu(d)*AIK_{k/d}(e(n/d): n multiple of d), where the * between MOEBIUS and AIK denotes Dirichlet convolution and (d_k(n): n >= 1) = AIK_k(e(n): n >= 1) has g.f. E(x)^k. (There is a typo in the given definition of CHK in the link.)

If C(x) is the g.f. of CHK(e(n): n >= 1) = Sum_{k = 1..n} CHK_k(e(n): n >= 1), then C(x) = Sum_{n>=1} Sum_{k = 1..n} c_k(n)*x^n = Sum_{k >= 1} (1/k) Sum_{n >= k} Sum_{d | gcd(n,k)} mu(d)*d_{k/d}(n/d)*x^n. Letting m = n/d and s = k/d and using the fact that E(0) = 0, we get C(x) = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} (1/s)*Sum_{m >= s} d_s(m)*(x^d)^m = Sum_{d >= 1} (mu(d)/d)*Sum_{s >= 1} E(x^d)^s. Thus, C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d)).

For the sequence (e(n): n >= 1) = (n: n >= 1), we have E(x) = Sum_{n>=1} n*x^n = x/(1 - x)^2, and thus A(x) = C(x) = -Sum_{d >= 1} (mu(d)/d)*log(1 - x/(1-x)^2), from which we can easily get the g.f. given in the formula section.

Apparently, for this sequence and for sequences A032165, A032166, A032167, the author assumes that C(0) = 0 (i.e., he assumes the CHK transform has no constant term), while for sequences A032164, A108529, and possibly others, he assumes that the CHK transform starts with the constant term 1 (i.e., he assumes C(x) = 1 - Sum_{d >= 1} (mu(d)/d)*log(1 - E(x^d))). (End)

From Petros Hadjicostas, Jul 13 2020: (Start)

We elaborate further on Michel Marcus's claim below. Consider his sequence (b(n): n >= 1) with b(1) = 3 and b(n) = a(n) for n >= 2.

Using the identity -Sum_{k >= 1} (mu(k)/k)*log(1 - x^k) = x for |x| < 1 and the g.f. of (a(n): n >= 1) below, we see that Sum_{n >= 1} b(n)*x^n = 3*x - a(1)*x + Sum_{n >= 1} a(n)*x^n = 2*x + Sum_{k >= 1} (mu(k)/k)*(2*log(1 - x^k) - log(1 - 3*x^k + x^(2*k))) = -Sum_{k >= 1} (mu(k)/k)*log(1 - 3*x^k + x^(2*k)).

Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.

Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) being the number of distinct primes of N).

For N = 6, a = phi(6)/2 + omega(6) = 2/2 + 2 = 3 and b = omega(6) - 1 = 1. It follows that D(w, N=6) = A001906(w+1) = Fibonacci(2*(w+1)).

For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.

For N = 6, we get that c(w, N=6) = A005248(w)/w.

He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)

Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).

For N = 6, we saw that a = 3 and b = 1, and hence d*(w, N=6) = b(w) for w >= 1 (as claimed by Michel Marcus below). See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..2400
• Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See line N = 6 in Table 1 (p. 6).
• C. G. Bower, Transforms (2).
• Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
• Eric Weisstein's World of Mathematics, Arnold's cat map.
• Wikipedia, Arnold's cat map.
• Index entries for sequences related to Lyndon words

Crossrefs

Cf. A000010, A001221, A001906, A004146, A032164, A032165, A032166, A032167, A032198, A005248, A108529, A113788.

Programs

Mathematica

Table[DivisorSum[n, MoebiusMu[n/#] (LucasL[2 #] - 2) &]/n, {n, 31}] (* Michael De Vlieger, Nov 18 2017 *)

Formula

a(n) = (1/n)*Sum_{d | n} mu(n/d)*A004146(d). - Vladeta Jovovic, Feb 15 2003

Inverse EULER transform of Fibonacci(2*n). - Vladeta Jovovic, May 04 2006

G.f.: Sum_{n >= 1} (mu(n)/n)*f(x^n), where f(y) = log((1 - y)^2/(1 - 3*y + y^2)). - Petros Hadjicostas, Nov 17 2017

It appears that the sequence b(1) = 3, b(n) = a(n) for n >= 2 is related to the rational sequence (c(w, N=6): w >= 1) = (A005248(w)/w: w >= 1) whose g.f. is log(1/(1 - a*t + b*t^2)), where a = phi(N)/2 + omega(N) and b = omega(N) - 1 when N = 6, where phi is A000010 and omega is A001221. See Kam Cheong Au (2020). - Michel Marcus, Jul 13 2020 [Edited by Petros Hadjicostas, Jul 13 2020]