

A092089


Number of oddlength palindromes among the ktuples of partial quotients of the continued fraction expansions of n/r, r = 1, ..., n.


4



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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


LINKS

Antti Karttunen, Table of n, a(n) for n = 1..10000
László Tóth, Menon's identity and arithmetical sums representing functions of several variables, Rend. Sem. Mat. Univ. Politec. Torino, 69 (2011), 97110 (see (37) in Corollary 15, p. 108).
Eric Weisstein's World of Mathematics, Partial quotient.


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(k1) if k>1 and g(k) = 2k+1 (This has been verified for n = 110000.) [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*(e1), if e > 1.  Michel Marcus, Jun 26 2014
Dirichlet g.f.: zeta(s)^3/zeta(2s)*((2^(3s)+5*2^s2)/(2^(3s)+2^(2s)).  Jianing Song, Mar 25 2019


EXAMPLE

[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.


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


PROG

(PARI) a(n) = if (n % 2, numdiv(n^2), if (n/2 % 2, 2*numdiv((n/2)^2), val = valuation(n, 2); 4*(val1)*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


CROSSREFS

Sequence in context: A080383 A086369 A337532 * A117659 A079065 A097272
Adjacent sequences: A092086 A092087 A092088 * A092090 A092091 A092092


KEYWORD

nonn,mult


AUTHOR

John W. Layman, Mar 29 2004


STATUS

approved



