A004125 - OEIS

%I M3213 #169 Oct 22 2023 00:44:20

%S 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,

%T 112,125,124,151,138,167,167,184,197,218,198,233,248,269,258,297,284,

%U 325,328,339,358,403,374,414,420,449,454,505,492,529,520,553,578,635,586,645,672

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

%C Row sums of A051778, A048158. Antidiagonal sums of A051127. - _L. Edson Jeffery_, Mar 03 2012

%C 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]

%C Also the alternating row sums of A236112. - _Omar E. Pol_, Jan 26 2014

%C If n is prime then a(n) = a(n-1) + n - 2. - _Omar E. Pol_, Mar 19 2014

%C If n is a power of 2 greater than 1, then a(n) = a(n-1). - _David Morales Marciel_, Oct 21 2015

%C It appears that if n is an even perfect number, then a(n) = a(n-1) - 1. - _Omar E. Pol_, Oct 21 2015

%C Partial sums of A235796. - _Omar E. Pol_, Jun 26 2016

%C 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

%C 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

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

%H N. J. A. Sloane, <a href="/A004125/b004125.txt">Table of n, a(n) for n = 1..2000</a> (first 1000 terms from T. D. Noe)

%H Jeffrey Shallit, <a href="http://www.jstor.org/stable/2321999">Problem E2817</a>, Amer. Math. Monthly, vol. 87, p 137, 1980.

%F 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

%F a(n) = A008805(n-3) + A049798(n-1), for n > 2. - _Carl Najafi_, Jan 31 2013

%F a(n) = A000217(n-1) - A153485(n). - _Omar E. Pol_, Jan 28 2014

%F 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

%F a(n) = Sum_{i=1..n} (n mod i). - _Wesley Ivan Hurt_, Sep 15 2017

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

%p 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

%t Table[Sum[Mod[n,k],{k,2,n-1}],{n,70}] (* _Harvey P. Dale_, Nov 23 2011 *)

%t Accumulate[Table[2n-1-DivisorSigma[1,n],{n,70}]] (* _Harvey P. Dale_, Jul 11 2014 *)

%o (PARI) A004125(n)=sum(k=2,n,n%k) \\ _M. F. Hasler_, Nov 22 2007

%o (Haskell)

%o a004125 n = sum $ map (mod n) [1..n]

%o -- _Reinhard Zumkeller_, Jan 28 2011

%o (Magma) [&+[n mod r: r in [1..n]]: n in [1..70]]; // _Bruno Berselli_, Jul 06 2014

%o (GAP) List([1..70],n->n^2-Sum([1..n],k->Sigma(k))); # _Muniru A Asiru_, Mar 28 2018

%o (Python)

%o def a(n): return sum(n%k for k in range(1, n))

%o print([a(n) for n in range(1, 63)]) # _Michael S. Branicky_, Jun 08 2021

%o (Python)

%o from math import isqrt

%o 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

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

%K nonn,easy,nice

%O 1,5

%A _N. J. A. Sloane_, _Jeffrey Shallit_

%E Edited by _M. F. Hasler_, Apr 18 2015