|
%I #49 Feb 21 2024 01:44:57
%S 0,2,3,6,5,15,7,20,18,35,11,54,13,63,60,72,17,117,19,130,105,143,23,
%T 204,75,195,135,238,29,345,31,272,231,323,210,450,37,399,312,500,41,
%U 651,43,550,495,575,47,792,196,775,510,754,53,999,440,924,627,899,59
%N Sum of numbers <= n which have common prime factors with n.
%C Sum of k <= n such that gcd(n,k) > 1.
%H Ivan Neretin, <a href="/A067392/b067392.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = n(n+1)/2 - n*phi(n)/2 = A000217(n)-A023896(n), for n>=2.
%F Not multiplicative.
%F a(p) = p where p is a prime; a(2^k) = 2^(k-1)*{2^(k-1) + 1).
%F G.f.: -Sum_{k>=2} mu(k)*k*x^k/(1 - x^k)^3. - _Ilya Gutkovskiy_, May 28 2019
%F Sum_{k=1..n} a(k) ~ (1/6 - 1/(Pi^2)) * n^3. - _Amiram Eldar_, Dec 03 2023
%e For n=24, a(24) = 2+3+4+6+8+9+10+12+14+15+16+18+20+21+22+24 = 204.
%t a[n_] := Plus@@Select[Range[1, n], GCD[ #, n]>1&]
%t Join[{0}, Table[n (n + 1) / 2 - n EulerPhi@(n) / 2, {n, 2, 60}]] (* _Vincenzo Librandi_, Jul 19 2019 *)
%o (PARI) A067392(n)={a=0; for(i=1, n, if(gcd(i, n)<>1, a=a+i)); a}
%o (PARI) a(n) = sum(k=1, n, k*(gcd(k, n) != 1)); \\ _Michel Marcus_, May 08 2018
%o (PARI) a(n) = if(n == 1, 0, n*(n + 1 - eulerphi(n))/2); \\ _Amiram Eldar_, Dec 03 2023
%o (Magma) [0] cat [n*(n+1)/2-n*EulerPhi(n)/2: n in [2..60]]; // _Vincenzo Librandi_, Jul 19 2019
%Y Cf. A000203, A000217, A023896, A024816.
%K nonn
%O 1,2
%A _Labos Elemer_, Jan 22 2002
|
