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,4

Links

Table of n, a(n) for n=1..65.

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

Crossrefs

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

Sequence in context: A190258 A161119 A019750 * A362952 A237289 A238396

Adjacent sequences: A308470 A308471 A308472 * A308474 A308475 A308476

Keyword

nonn

Author

Ilya Gutkovskiy, May 29 2019

Status

approved