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

0, 2, 3, 6, 5, 15, 7, 20, 18, 35, 11, 54, 13, 63, 60, 72, 17, 117, 19, 130, 105, 143, 23, 204, 75, 195, 135, 238, 29, 345, 31, 272, 231, 323, 210, 450, 37, 399, 312, 500, 41, 651, 43, 550, 495, 575, 47, 792, 196, 775, 510, 754, 53, 999, 440, 924, 627, 899, 59

Offset: 1

Author

Labos Elemer, Jan 22 2002

Keywords

• nonn
• easy

Comments

Sum of k <= n such that gcd(n,k) > 1.

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

Examples

			For n=24, a(24) = 2+3+4+6+8+9+10+12+14+15+16+18+20+21+22+24 = 204.
		

Links

• Ivan Neretin, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000203, A000217, A023896, A024816.

Programs

Magma

[0] cat [n*(n+1)/2-n*EulerPhi(n)/2: n in [2..60]]; // Vincenzo Librandi, Jul 19 2019

Mathematica

a[n_] := Plus@@Select[Range[1, n], GCD[ #, n]>1&]
Join[{0}, Table[n (n + 1) / 2 - n EulerPhi@(n) / 2, {n, 2, 60}]] (* Vincenzo Librandi, Jul 19 2019 *)

PARI

A067392(n)={a=0; for(i=1, n, if(gcd(i, n)<>1, a=a+i)); a}

PARI

a(n) = sum(k=1, n, k*(gcd(k, n) != 1)); \\ Michel Marcus, May 08 2018

PARI

a(n) = if(n == 1, 0, n*(n + 1 - eulerphi(n))/2); \\ Amiram Eldar, Dec 03 2023

Formula

a(n) = n(n+1)/2 - n*phi(n)/2 = A000217(n)-A023896(n), for n>=2.

Not multiplicative.

a(p) = p where p is a prime; a(2^k) = 2^(k-1)*(2^(k-1) + 1).

G.f.: -Sum_{k>=2} mu(k)*k*x^k/(1 - x^k)^3. - Ilya Gutkovskiy, May 28 2019

Sum_{k=1..n} a(k) ~ (1/6 - 1/(Pi^2)) * n^3. - Amiram Eldar, Dec 03 2023