A308473 - OEIS

%I #15 Nov 06 2023 16:41:16

%S 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,

%T 108,210,0,315,0,240,198,289,175,414,0,361,273,460,0,609,0,506,450,

%U 529,0,744,147,725,459,702,0,945,385,868,570,841,0,1290,0,961,819,992,520

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

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

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

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

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

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

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

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

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

%t 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

%t a[n_] := Sum[If[GCD[n, k] > 1, k, 0], {k, 1, n - 1}]; Table[a[n], {n, 1, 65}]

%t Join[{0}, Table[n (n - EulerPhi[n] - 1)/2, {n, 2, 65}]]

%o (PARI) a(n) = sum(k=1, n-1, if (gcd(n,k)>1, k)); \\ _Michel Marcus_, May 31 2019

%o (Python)

%o from sympy import totient

%o def A308473(n): return n*(n-totient(n)-1)>>1 if n>1 else 0 # _Chai Wah Wu_, Nov 06 2023

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

%K nonn

%O 1,4

%A _Ilya Gutkovskiy_, May 29 2019