A069828 Sum of positive integers k for k <= n and gcd(k,n) = gcd(k+1,n).

1, 0, 1, 0, 6, 0, 15, 0, 12, 0, 45, 0, 66, 0, 21, 0, 120, 0, 153, 0, 50, 0, 231, 0, 180, 0, 117, 0, 378, 0, 435, 0, 144, 0, 255, 0, 630, 0, 209, 0, 780, 0, 861, 0, 198, 0, 1035, 0, 840, 0, 375, 0, 1326, 0, 729, 0, 476, 0, 1653, 0, 1770, 0, 465, 0, 1056, 0, 2145, 0, 714, 0, 2415

Offset: 1

Author

Vladeta Jovovic, Apr 29 2002

Keywords

• nonn

Crossrefs

Cf. A058026, A065474, A070555.

Programs

Mathematica

f[p_, e_] := (p-2) * p^(e-1); a[1] = 1; a[n_] := ((n-1)/2) * Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, May 23 2025 *)

PARI

a(n) = if (n==1, 1, n*(n-1)/2*sumdiv(n, d, moebius(d)*numdiv(d)/d)) \\ Michel Marcus, Jun 17 2013

PARI

a(n) = if(n == 1, 1, my(f = factor(n)); ((n-1)*n/2) * prod(i = 1, #f~, (f[i,1]-2) / f[i,1])); \\ Amiram Eldar, May 23 2025

Formula

a(n) = (n*(n-1)/2)*Sum_{d|n} mu(d)*tau(d)/d, n > 1.

From Amiram Eldar, May 23 2025: (Start)

a(n) = (n-1)*A058026(n)/2 for n >= 2.

Sum_{k=1..n} a(k) ~ c * n^2 / 6, where c = A065474. (End)