A092089 Number of odd-length palindromes among the k-tuples of partial quotients of the continued fraction expansions of n/r, r = 1, ..., n.

1, 2, 3, 4, 3, 6, 3, 8, 5, 6, 3, 12, 3, 6, 9, 12, 3, 10, 3, 12, 9, 6, 3, 24, 5, 6, 7, 12, 3, 18, 3, 16, 9, 6, 9, 20, 3, 6, 9, 24, 3, 18, 3, 12, 15, 6, 3, 36, 5, 10, 9, 12, 3, 14, 9, 24, 9, 6, 3, 36, 3, 6, 15, 20, 9, 18, 3, 12, 9, 18, 3, 40, 3, 6, 15, 12, 9, 18, 3, 36, 9, 6, 3, 36, 9, 6, 9, 24, 3

Offset: 1

Author

John W. Layman, Mar 29 2004

Keywords

• nonn
• easy
• mult

Comments

Suggested by R. K. Guy, Mar 26 2004

From Jianing Song, Mar 24 2019: (Start)

a(n) is also the number of inequivalent residue classes modulo n where the equivalence relation is defined as [a] ~ [b] (mod n) if and only if there exists some k such that gcd(k, n) = 1 and that a*k^2 == b (mod n). For example, for n = 16, the inequivalent residue classes are {[0], [1], [2], [3], [4], [5], [6], [7], [8], [10], [12], [14]}, so a(16) = 14.

Proof: let S(n) be the set of inequivalent residue classes modulo n, so our goal is to show that |S(n)| = a(n) for all n. By the Chinese Remainder Theorem, if gcd(s, t) = 1, then [a] ~ [b] (mod s*t) if and only if [a] ~ [b] (mod s) and [a] ~ [b] (mod t), so there is a one-to-one correspondence between S(s*t) and S(s) X S(t), that is, |S(n)| is multiplicative. It is obvious that |S(p^e)| = a(p^e), so |S(n)| = a(n) for all n. (End)

Examples

			[1, 2, 1, 2, 1] <-> 1+1/(2+1/(1+1/(2+1/1))) = 15/11 is one of the nine palindromes {[15], [5], [3, 1, 3], [3], [1, 1, 1], [1, 2, 1, 2, 1], [1, 3, 1], [1, 13, 1], [1]} among the continued fraction expansions of 15/r for r = 1..15. Thus a(15)=9.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000
• Agustina Czenky, Diagramatics for cyclic pointed fusion categories, arXiv:2404.08084 [math.QA], 2024. See p. 15.
• 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 (see (37) in Corollary 15, p. 108).
• Eric Weisstein's World of Mathematics, Partial quotient.

Crossrefs

Cf. A001620, A201994, A306016.

Programs

Mathematica

Table[Apply[Times, FactorInteger[n] /. {p_, e_} /; p > 0 :> Which[p == 1, 1, OddQ@ p, 2 e + 1, And[p == 2, e == 1], 2, True, 4 (e - 1)]], {n, 89}] (* Michael De Vlieger, Sep 11 2017 *)

PARI

a(n) = if (n % 2, numdiv(n^2), if (n/2 % 2, 2*numdiv((n/2)^2), val = valuation(n, 2); 4*(val-1)*numdiv((n/2^val)^2))); \\ Michel Marcus, Jun 26 2014

Scheme

(define (A092089 n) (cond ((= 1 n) n) ((zero? (modulo n 4)) (* 4 (+ -1 (A067029 n)) (A092089 (A000265 n)))) ((even? n) (* 2 (A092089 (/ n 2)))) (else (* (+ 1 (* 2 (A067029 n))) (A092089 (A028234 n)))))) ;; Antti Karttunen, Sep 11 2017

Formula

Conjecture: Let n = (2^k0)*(p1^k1)*(p2^k2)*...*(pm^km) be the prime factorization of n where p1, p2, ..., pm are distinct primes. Then a(n) is multiplicative and is given by a(n) = f(k0)*g(k1)*g(k2)*...*g(km), where f(0) = 1, f(1) = 2, f(k) = 4(k-1) if k>1 and g(k) = 2k+1 (This has been verified for n = 1-10000.) [Corrected by Jianing Song, Mar 24 2019]

Multiplicative with a(p^e) = 2e+1 if p is odd; a(2) = 2, a(2^e)= 4*(e-1), if e > 1. - Michel Marcus, Jun 26 2014

Dirichlet g.f.: zeta(s)^3/zeta(2*s) * (1 - 1/2^s + 1/2^(2*s-1)). - Jianing Song, Mar 25 2019 [corrected by Amiram Eldar, Dec 18 2023]

Sum_{k=1..n} a(k) ~ (3/Pi^2) * n * (log(n^2) + c_1 * log(n) + c_2), where c_1 = 6 * gamma - 2 - log(2) - 4*zeta'(2)/zeta(2) = 3.04999078122..., gamma is Euler's constant (A001620), c_2 = 2 - 6 * gamma + 6 * gamma^2 + log(2) - 3 * gamma * log(2) + 3*log(2)^2/2 - 6 *gamma_1 + 4*zeta'(2)/zeta(2) + (2 * log(2) - 12 * gamma) * zeta'(2)/zeta(2) + 8 * (zeta'(2)/zeta(2))^2 - 4 * zeta''(2)/zeta(2) = -0.1743888255..., and gamma_1 is the 1st Stieltjes constant (A082633). - Amiram Eldar, Dec 18 2023