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

Links

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

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)

Example

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.

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

Prog

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

Crossrefs

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

Cf. A072514, A008683.

Sequence in context: A143820 A259930 A103553 * A116924 A327957 A335707

Adjacent sequences: A067436 A067437 A067438 * A067440 A067441 A067442

Keyword

nonn

Author

Amarnath Murthy, Jan 29 2002

Extensions

Edited by Dean Hickerson, Feb 15 2002

Status

approved