|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
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]
If n is prime then a(n) = a(n-1) + n - 2. - Omar E. Pol, Mar 19 2014
It appears that if n is an even perfect number, then a(n) = a(n-1) - 1. - Omar E. Pol, Oct 21 2015
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
|
Jeffrey Shallit, Problem E2817, Amer. Math. Monthly, vol. 87, p 137, 1980.
|
|
FORMULA
|
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
|
|
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
|
(Haskell)
a004125 n = sum $ map (mod n) [1..n]
(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))
(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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|