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,2

Comments

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

Links

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

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

Example

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

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 *)

Prog

(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
(Magma) [0] cat [n*(n+1)/2-n*EulerPhi(n)/2: n in [2..60]]; // Vincenzo Librandi, Jul 19 2019

Crossrefs

Cf. A000203, A000217, A023896, A024816.

Sequence in context: A136183 A100211 A071257 * A066449 A276942 A255483

Adjacent sequences: A067389 A067390 A067391 * A067393 A067394 A067395

Keyword

nonn

Author

Labos Elemer, Jan 22 2002

Status

approved