A308473 Sum of numbers < n which have common prime factors with n.

0, 0, 0, 2, 0, 9, 0, 12, 9, 25, 0, 42, 0, 49, 45, 56, 0, 99, 0, 110, 84, 121, 0, 180, 50, 169, 108, 210, 0, 315, 0, 240, 198, 289, 175, 414, 0, 361, 273, 460, 0, 609, 0, 506, 450, 529, 0, 744, 147, 725, 459, 702, 0, 945, 385, 868, 570, 841, 0, 1290, 0, 961, 819, 992, 520

Offset: 1

Author

Ilya Gutkovskiy, May 29 2019

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A000010, A000217, A001065, A008578, A008683, A016035, A023896, A024816, A051953, A067392, A109607.

Programs

Mathematica

nmax = 65; CoefficientList[Series[-x^2 (2 - x)/(1 - x)^2 - Sum[MoebiusMu[k] k x^k/(1 - x^k)^3, {k, 2, nmax}], {x, 0, nmax}], x] // Rest
a[n_] := Sum[If[GCD[n, k] > 1, k, 0], {k, 1, n - 1}]; Table[a[n], {n, 1, 65}]
Join[{0}, Table[n (n - EulerPhi[n] - 1)/2, {n, 2, 65}]]

PARI

a(n) = sum(k=1, n-1, if (gcd(n,k)>1, k)); \\ Michel Marcus, May 31 2019

Python

from sympy import totient
def A308473(n): return n*(n-totient(n)-1)>>1 if n>1 else 0 # Chai Wah Wu, Nov 06 2023

Formula

G.f.: -x^2*(2 - x)/(1 - x)^2 - Sum_{k>=2} mu(k)*k*x^k/(1 - x^k)^3.

a(n) = Sum_{k=1..n-1, gcd(n,k) > 1} k.

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

a(n) = n*A016035(n)/2.

a(n) = A000217(n-1) - A023896(n) for n > 1.

a(n) = A067392(n) - n for n > 1.

a(n) = 0 if n is in A008578.

Sum_{k=1..n} a(k) ~ (1/6 - 1/Pi^2)*n^3. - Vaclav Kotesovec, May 30 2019