A004125 Sum of remainders of n mod k, for k = 1, 2, 3, ..., n.

0, 0, 1, 1, 4, 3, 8, 8, 12, 13, 22, 17, 28, 31, 36, 36, 51, 47, 64, 61, 70, 77, 98, 85, 103, 112, 125, 124, 151, 138, 167, 167, 184, 197, 218, 198, 233, 248, 269, 258, 297, 284, 325, 328, 339, 358, 403, 374, 414, 420, 449, 454, 505, 492, 529, 520, 553, 578, 635, 586, 645, 672

Offset: 1

Author

N. J. A. Sloane, Jeffrey Shallit

Keywords

• nonn
• easy
• nice

Comments

Row sums of A051778, A048158. Antidiagonal sums of A051127. - L. Edson Jeffery, Mar 03 2012

Let u_m(n) = Sum_{k=1..n} (n^m mod k^m) with m integer. As n-->+oo, u_m(n) ~ (n^(m+1))*(1-(1/(m+1))*Zeta(1+1/m)). Proof: using Riemann sums, we have u_m(n) ~ (n^(m+1))*int(((1/x)[nonascii character here])*(1-floor(x^m)/(x^m)),x=1..+oo) and the result follows. - Yalcin Aktar, Jul 30 2008 [x is the real variable of integration. The nonascii character (which was illegible in the original message) is probably some form of multiplication sign. I suggest that we leave it the way it is for now. - N. J. A. Sloane, Dec 07 2014]

Also the alternating row sums of A236112. - Omar E. Pol, Jan 26 2014

If n is prime then a(n) = a(n-1) + n - 2. - Omar E. Pol, Mar 19 2014

If n is a power of 2 greater than 1, then a(n) = a(n-1). - David Morales Marciel, Oct 21 2015

It appears that if n is an even perfect number, then a(n) = a(n-1) - 1. - Omar E. Pol, Oct 21 2015

Partial sums of A235796. - Omar E. Pol, Jun 26 2016

Aside from a(n) = a(n-1) for n = 2^m, the only values appearing more than once among the first 6*10^8 terms are those at n = 38184 +- 1, 458010 +- 1, 776112 +- 1, 65675408 +- 1, and 113393280 +- 2. - Trevor Cappallo, Jun 07 2021

The off-by-1 terms in the comment above are the terms of A068077. Proof: If a(n-1) = a(n+1), then (n-1)^2 - Sum_{k=1..n-1} sigma(k) = (n+1)^2 - Sum_{k=1..n+1} sigma(k) via the formula; rearranging terms gives sigma(n)+sigma(n+1)=4n. - Lewis Chen, Sep 24 2021

Examples

			a(5) = 4. The remainder when 5 is divided by 2,3,4 respectively is 1,2,1 and their sum = 4.
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..2000 (first 1000 terms from T. D. Noe)
• Jeffrey Shallit, Problem E2817, Amer. Math. Monthly, vol. 87, p 137, 1980.

Crossrefs

Cf. A000290, A006218, A023196, A048158, A050482, A051778, A120444 (first differences).

Cf. A067439, A072514, A111490.

Programs

GAP

List([1..70],n->n^2-Sum([1..n],k->Sigma(k))); # Muniru A Asiru, Mar 28 2018

Haskell

a004125 n = sum $ map (mod n) [1..n]
-- Reinhard Zumkeller, Jan 28 2011

Magma

[&+[n mod r: r in [1..n]]: n in [1..70]]; // Bruno Berselli, Jul 06 2014

Maple

A004125 := n -> add( modp(n,k), k=2..n); /* much faster and unambiguous; "a mod b" may be mods(a,b) */ # M. F. Hasler, Nov 22 2007

Mathematica

Table[Sum[Mod[n,k],{k,2,n-1}],{n,70}] (* Harvey P. Dale, Nov 23 2011 *)
Accumulate[Table[2n-1-DivisorSigma[1,n],{n,70}]] (* Harvey P. Dale, Jul 11 2014 *)

PARI

A004125(n)=sum(k=2,n,n%k) \\ M. F. Hasler, Nov 22 2007

Python

def a(n): return sum(n%k for k in range(1, n))
print([a(n) for n in range(1, 63)]) # Michael S. Branicky, Jun 08 2021

Python

from math import isqrt
def A004125(n): return n**2+((s:=isqrt(n))**2*(s+1)-sum((q:=n//k)*((k<<1)+q+1) for k in range(1,s+1))>>1) # Chai Wah Wu, Oct 21 2023

SageMath

def a(n): return sum(n.mod(k) for k in (1..n))
print([a(n) for n in (1..62)])  # Peter Luschny, May 12 2025

Formula

a(n) = n^2 - Sum_{k=1..n} sigma(k) = A000290(n) - A024916(n), hence asymptotically a(n) = n^2*(1-Pi^2/12) + O(n*log(n)^(2/3)). - Benoit Cloitre, Apr 28 2002. Asymptotics corrected/improved by Charles R Greathouse IV, Feb 22 2015

a(n) = A008805(n-3) + A049798(n-1), for n > 2. - Carl Najafi, Jan 31 2013

a(n) = A000217(n-1) - A153485(n). - Omar E. Pol, Jan 28 2014

G.f.: x^2/(1-x)^3 - (1-x)^(-1) * Sum_{k>=1} k*x^(2*k)/(1-x^k). - Robert Israel, Aug 13 2015

a(n) = Sum_{i=1..n} (n mod i). - Wesley Ivan Hurt, Sep 15 2017

From Ridouane Oudra, May 12 2025: (Start)

a(n) = A067439(n) + A072514(n).

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

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

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

a(n) = A111490(n) - n. - Peter Luschny, May 12 2025

Extensions

Edited by M. F. Hasler, Apr 18 2015