login
A308473
Sum of numbers < n which have common prime factors with n.
1
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,4
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
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}]]
PROG
(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
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, May 29 2019
STATUS
approved