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 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)
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.
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
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*(val-1)*numdiv((n/2^val)^2))); \\ Michel Marcus, Jun 26 2014
CROSSREFS
KEYWORD
nonn,easy,mult
AUTHOR
John W. Layman, Mar 29 2004
STATUS
approved