A060992 a(n) = Sum_{gcd(i,j) | 0 < i <= j < n and i+j = n}.

0, 1, 1, 3, 2, 6, 3, 8, 6, 11, 5, 17, 6, 16, 15, 20, 8, 27, 9, 31, 22, 26, 11, 44, 20, 31, 27, 45, 14, 60, 15, 48, 36, 41, 41, 75, 18, 46, 43, 80, 20, 87, 21, 73, 72, 56, 23, 108, 42, 85, 57, 87, 26, 108, 67, 116, 64, 71, 29, 165, 30, 76

Offset

1,4

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

a(n) = Sum_{d divides n} floor(d/2)*phi(n/d). a(p) = (p-1)/2 for an odd prime p. - Vladeta Jovovic, Dec 21 2004

a(n) = Sum_{i=1..floor(n/2)} gcd(n-i,i). - Wesley Ivan Hurt, Nov 12 2017

G.f.: Sum_{k>=1} phi(k)*x^(2*k)/((1 + x^k)*(1 - x^k)^2). - Ilya Gutkovskiy, Oct 24 2018

Example

a(12) = gcd(1,11) + gcd(2,10) + gcd(3,9) + gcd(4,8) + gcd(5,7) + gcd(6,6) = 1 + 2 + 3 + 4 + 1 + 6 = 17;
a(13) = gcd(1,12) + gcd(2,11) + gcd(3,10) + gcd(4,9) + gcd(5,8) + gcd(6,7) = 1 + 1 + 1 + 1 + 1 + 1 = 6.

Maple

N:= 200: # to get a(1)..a(N)
A:= Vector(N):
for d from 1 to N do
  c:= floor(d/2);
  for n from d to N by d do
    A[n]:= A[n]+c*numtheory:-phi(n/d)
  od
od:
seq(A[i], i=1..N); # Robert Israel, May 11 2018

Mathematica

Table[Sum[GCD[n - i, i], {i, Floor[n/2]}], {n, 100}] (* Wesley Ivan Hurt, Nov 12 2017 *)

Prog

(PARI) a(n) = sumdiv(n, d, (d\2)*eulerphi(n/d)); \\ Michel Marcus, May 11 2018

Crossrefs

Cf. A234307.

Sequence in context: A334667 A245676 A341516 * A064455 A141619 A270143

Adjacent sequences: A060989 A060990 A060991 * A060993 A060994 A060995

Keyword

nonn,easy,look

Author

Reinhard Zumkeller, Feb 14 2002

Status

approved