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

Author

Vladeta Jovovic, Dec 30 2002

Keywords

• mult
• nonn

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)
• 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.

Crossrefs

Cf. A018804, A069097, A069193.

Cf. A245717.

Programs

Haskell

a078430 = sum . a245717_row  -- Reinhard Zumkeller, Jul 30 2014

Mathematica

Table[Sum[GCD[k^2,n],{k,n}],{n,70}] (* Harvey P. Dale, Sep 29 2014 *)
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 *)

PARI

a(n) = sum(k=1,n, gcd(k^2, n)); \\ Michel Marcus, Aug 03 2016

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