A072514 Sum of n mod k for k in {1...n} with gcd(k,n) > 1.

0, 0, 0, 0, 0, 2, 0, 2, 3, 8, 0, 9, 0, 16, 17, 16, 0, 27, 0, 31, 31, 44, 0, 52, 20, 56, 36, 69, 0, 92, 0, 72, 77, 102, 68, 127, 0, 128, 97, 152, 0, 192, 0, 165, 153, 196, 0, 230, 56, 231, 170, 237, 0, 319, 154, 290, 211, 302, 0, 421, 0, 334, 273, 334, 192, 478, 0, 411, 317

Offset: 1

Author

Amarnath Murthy, Jul 30 2002

Keywords

• nonn

Comments

Previous name was: Sum of the remainders when n is divided by unrelated numbers (numbers which are neither coprime to n nor divide n).

Examples

			a(18) = 27: the unrelated numbers to 18 are 4, 8, 10, 12, 14, 15 and 16. The remainders when 18 is divided by these numbers are 2, 2, 8, 6, 4, 3 and 2 whose sum is 27.
		

Links

• Paolo P. Lava, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A004125, A067439, A008683, A111490.

Programs

Maple

seq(add(n mod k, k=select(j->gcd(j,n)>1, [$1..n])),n=1..69); # Peter Luschny, Oct 01 2014

Mathematica

snmk[n_]:=Total[Mod[n,Complement[Complement[Range[n],Divisors[n]], Select[ Range[n], CoprimeQ[ #,n]&]]]]; Array[snmk,70] (* Harvey P. Dale, Dec 09 2018 *)

PARI

lista(nn) = vector(nn, n, sum(i=1, n, (n % i)*(gcd(n, i) != 1))); \\ Michel Marcus, Oct 01 2014

Formula

From Ridouane Oudra, May 14 2025: (Start)

a(n) = A004125(n) - A067439(n).

a(n) = Sum_{d|n, d>1} d*A067439(n/d).

a(p) = 0, for p prime.

a(p*q) = p*A067439(q) + q*A067439(p), for p and q two distinct prime numbers.

a(p^k) = p*A004125(p^(k-1)), for p a prime and k >= 0. (End)

Extensions

Corrected and extended by David Garber, Oct 22 2002

New name from Robert Israel, Oct 01 2014