A067439 a(n) = sum of all the remainders when n is divided by positive integers less than and coprime to n.

0, 0, 1, 1, 4, 1, 8, 6, 9, 5, 22, 8, 28, 15, 19, 20, 51, 20, 64, 30, 39, 33, 98, 33, 83, 56, 89, 55, 151, 46, 167, 95, 107, 95, 150, 71, 233, 120, 172, 106, 297, 92, 325, 163, 186, 162, 403, 144, 358, 189, 279, 217, 505, 173, 375, 230, 342, 276, 635, 165, 645, 338

Offset: 1

Author

Amarnath Murthy, Jan 29 2002

Keywords

• nonn

Examples

			a(8) = 6. The remainders when 8 is divided by the coprime numbers 1, 3, 5 and 7 are 0, 2, 3 and 1, whose sum = 6.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A004125, A067435, A067436, A024934, A033955, A111490.

Cf. A072514, A008683.

Programs

Maple

a := n -> add(ifelse(igcd(n, i) = 1, irem(n, i), 0), i = 1..n-1):
seq(a(n), n = 1..62);  # Peter Luschny, May 14 2025

Mathematica

a[n_] := Sum[If[GCD[i, n]>1, 0, Mod[n, i]], {i, 1, n-1}]
Table[Total[Mod[n,#]&/@Select[Range[n-1],CoprimeQ[#,n]&]],{n,70}] (* Harvey P. Dale, May 22 2012 *)

PARI

a(n)=sum(i=1,n-1,if(gcd(n,i)==1,n%i)) \\ Charles R Greathouse IV, Jul 17 2012

Formula

From Ridouane Oudra, May 14 2025: (Start)

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

a(n) = Sum_{d|n} d*mu(d)*A004125(n/d).

a(n) = Sum_{d|n} mu(d)*f(n,d), where f(n,d) = Sum_{i=1..n/d} (n mod d*i).

a(p) = A004125(p), for p prime.

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

a(p^k) = A072514(p^(k+1))/p - A072514(p^k), for p prime and k >= 0. (End)

Extensions

Edited by Dean Hickerson, Feb 15 2002