cp's OEIS Frontend

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

%I A308473 #19 Jan 22 2025 12:02:13
%S A308473 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 A308473 108,210,0,315,0,240,198,289,175,414,0,361,273,460,0,609,0,506,450,
%U A308473 529,0,744,147,725,459,702,0,945,385,868,570,841,0,1290,0,961,819,992,520
%N A308473 Sum of numbers < n which have common prime factors with n.
%H A308473 Antti Karttunen, <a href="/A308473/b308473.txt">Table of n, a(n) for n = 1..20000</a>
%F A308473 G.f.: -x^2*(2 - x)/(1 - x)^2 - Sum_{k>=2} mu(k)*k*x^k/(1 - x^k)^3.
%F A308473 a(n) = Sum_{k=1..n-1, gcd(n,k) > 1} k.
%F A308473 a(n) = n*(n - phi(n) - 1)/2 for n > 1
%F A308473 a(n) = n*A016035(n)/2.
%F A308473 a(n) = A000217(n-1) - A023896(n) for n > 1.
%F A308473 a(n) = A067392(n) - n for n > 1.
%F A308473 a(n) = 0 if n is in A008578.
%F A308473 Sum_{k=1..n} a(k) ~ (1/6 - 1/Pi^2)*n^3. - _Vaclav Kotesovec_, May 30 2019
%t A308473 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 A308473 a[n_] := Sum[If[GCD[n, k] > 1, k, 0], {k, 1, n - 1}]; Table[a[n], {n, 1, 65}]
%t A308473 Join[{0}, Table[n (n - EulerPhi[n] - 1)/2, {n, 2, 65}]]
%o A308473 (PARI) a(n) = sum(k=1, n-1, if (gcd(n,k)>1, k)); \\ _Michel Marcus_, May 31 2019
%o A308473 (Python)
%o A308473 from sympy import totient
%o A308473 def A308473(n): return n*(n-totient(n)-1)>>1 if n>1 else 0 # _Chai Wah Wu_, Nov 06 2023
%Y A308473 Cf. A000010, A000217, A001065, A008578, A008683, A016035, A023896, A024816, A051953, A067392, A109607.
%K A308473 nonn
%O A308473 1,4
%A A308473 _Ilya Gutkovskiy_, May 29 2019