A078430 Sum of gcd(k^2,n) for 1 <= k <= n.

1, 3, 5, 10, 9, 15, 13, 28, 33, 27, 21, 50, 25, 39, 45, 88, 33, 99, 37, 90, 65, 63, 45, 140, 145, 75, 153, 130, 57, 135, 61, 240, 105, 99, 117, 330, 73, 111, 125, 252, 81, 195, 85, 210, 297, 135, 93, 440, 385, 435, 165, 250, 105, 459, 189, 364, 185, 171, 117, 450, 121

Offset

1,2

Comments

a(n) is the number of non-congruent solutions to x^2*y = 0 mod n. - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 17 2003

Row sums of triangle A245717. - Reinhard Zumkeller, Jul 30 2014

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Reinhard Zumkeller)

Vaclav Kotesovec, Graph - the asymptotic ratio (100000 terms)

E. Krätzel, W. G. Nowak, and L. Tóth, On certain arithmetic functions involving the greatest common divisor, Cent. Eur. J. Math., 10 (2012), 761-774.

M. Kühleitner and W. G. Nowak, On a question of A. Schinzel: Omega estimates for a special type of arithmetic functions , arXiv: 1204.1146 [math.NT], 2012.

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.

Formula

a(n) is multiplicative. G.f. for a(p^n), p a prime, is given by (1+(p-1)*x-p^2*x^2)/(1-p*x)/(1-p^3*x^2).

a(n) = n*Sum_{d|n} phi(d)*N(d)/d, where phi is Euler's totient function A000010 and N(n) is sequence A000188. - Laszlo Toth, Apr 15 2012

Multiplicative with a(p^e) = p^(3*e/2) + p^(3*e/2-1) - p^(e-1) if e is even, and 2*p^((3*e-1)/2) - p^(e-1) if e is odd. - Amiram Eldar, Apr 28 2023

From Vaclav Kotesovec, Jul 08 2026: (Start)

Let f(s) = Product_{primes p} (1 + 1/p^(3*s-3) + (1 - 2*p)/p^(2*s-1) - 1/p^s).

Dirichlet g.f.: zeta(s-1)^2 * zeta(2*s-3) * f(s).

Sum_{k=1..n} a(k) ~ (log(n)^2 + (8*gamma - 1 + 2*f'(2)/f(2))*log(n) + 1/2 - 4*gamma + 10*gamma^2 - 12*sg1 + ((8*gamma - 1)*f'(2) + f''(2))/f(2)) * n^2*f(2)/8, where

f(2) = Product_{primes p} (1 - 3/p^2 + 2/p^3) = A065473 = 0.28674742843447873410...,

f'(2) = f(2) * Sum_{primes p} 5*log(p)/(p^2+p-2) = 0.668602820635914552372333261...,

f''(2) = f'(2)^2/f(2) + f(2) * Sum_{primes p} (-9*p^2-5*p+1)*log(p)^2/(p^2+p-2)^2 = -0.32230122475638695309490561...,

gamma is the Euler-Mascheroni constant A001620 and sg1 is the first Stieltjes constant (see A082633). (End)

Mathematica

Table[Sum[GCD[k^2, n], {k, n}], {n, 70}] (* Harvey P. Dale, Sep 29 2014 *)
(* Alternative: *)
f[p_, e_] := If[EvenQ[e], p^(3*e/2) + p^(3*e/2 - 1), 2*p^((3*e - 1)/2)] - p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

Prog

(Haskell)
a078430 = sum . a245717_row  -- Reinhard Zumkeller, Jul 30 2014
(PARI) a(n) = sum(k=1, n, gcd(k^2, n)); \\ Michel Marcus, Aug 03 2016

Crossrefs

Cf. A018804, A069097, A069193.

Cf. A245717, A065473.

Sequence in context: A286592 A176629 A069193 * A372882 A393808 A397733

Adjacent sequences: A078427 A078428 A078429 * A078431 A078432 A078433

Keyword

mult,nonn

Author

Vladeta Jovovic, Dec 30 2002

Status

approved