A067392 - OEIS

%I #58 Aug 18 2024 23:04:12

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

%C V. S. Guba conjectured that for any positive n and prime p, a(n) != a(n+p). - _Max Alekseyev_, May 08 2024

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

%O 1,2

%A _Labos Elemer_, Jan 22 2002