login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A004125
Sum of remainders of n mod k, for k = 1, 2, 3, ..., n.
(Formerly M3213)
86
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,5
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
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.
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
EXAMPLE
a(5) = 4. The remainder when 5 is divided by 2,3,4 respectively is 1,2,1 and their sum = 4.
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 *)
PROG
(PARI) A004125(n)=sum(k=2, n, n%k) \\ M. F. Hasler, Nov 22 2007
(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
(GAP) List([1..70], n->n^2-Sum([1..n], k->Sigma(k))); # Muniru A Asiru, Mar 28 2018
(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
CROSSREFS
Cf. A000290, A006218, A023196, A048158, A050482, A051778, A120444 (first differences).
Sequence in context: A021699 A131416 A134390 * A137924 A171527 A240969
KEYWORD
nonn,easy,nice
EXTENSIONS
Edited by M. F. Hasler, Apr 18 2015
STATUS
approved