A333297 a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} i.

1, 4, 13, 25, 55, 73, 136, 184, 265, 325, 490, 562, 796, 922, 1102, 1294, 1702, 1864, 2377, 2617, 2995, 3325, 4084, 4372, 5122, 5590, 6319, 6823, 8041, 8401, 9796, 10564, 11554, 12370, 13630, 14278, 16276, 17302, 18706, 19666, 22126, 22882, 25591, 26911, 28531, 30049, 33292, 34444, 37531, 39031

Offset: 1

Author

N. J. A. Sloane, Mar 25 2020

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A002618, A023896, A115004, A018805, A319087, A333295.

Programs

Maple

Vi := proc(m,n) local a,i,j; a:=0;
for i from 1 to m do for j from 1 to n do
if igcd(i,j)=1 then a:=a+i; fi; od: od: a; end;
# the diagonal :
[seq(Vi(n,n),n=1..50)];
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      a(n-1) + 3*n*numtheory[phi](n)/2)
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Mar 25 2020

Mathematica

a[n_] := a[n] = If[n < 2, n, a[n - 1] + 3 n EulerPhi[n]/2];
Array[a, 50] (* Jean-François Alcover, Nov 27 2020, after Alois P. Heinz *)

PARI

a(n)={my(s=0);for(i=1,n,for(j=1,n,if(gcd(i,j)==1,s+=i)));s};
for(k=1,45,print1(a(k),", ")) \\ Hugo Pfoertner, Mar 25 2020

Formula

From Alois P. Heinz, Mar 25 2020: (Start)

a(n) = a(n-1) + 3*n*phi(n)/2 for n > 1, a(n) = n for n <= 1.

a(n) = 1 + Sum_{k=2..n} 3*k*phi(k)/2. (End)

a(n) = a(n-1) + 3 * A023896(n) for n > 1. - Hugo Pfoertner, Mar 26 2020

a(n) ~ (3/Pi^2) * n^3. - Amiram Eldar, Dec 01 2024