I'm trying to get a closed form for $$f(n) = \sum_{k=0}^{n-1}\sum_{r=0}^{k-1}\left\lfloor\frac{kr}{n-1} \right\rfloor$$

It is fairly obvious that for large $n$ this grows like $\frac{n^2}{6}$ but for a step in a problem I am working I need this in in some sort of closed form, or at least a simpler form or single sum.

When I try it, totients come into the picture, but I seem to get ugly sums of totients, and that is not much better than the original double sum.

It doesn't seem like this should be so tough.

  • $\begingroup$ I can't reproduce the growth you mention. What are the first few values of $f(n)$? $\endgroup$ – lhf Dec 3 '14 at 0:38
  • $\begingroup$ I get $0,0,1,3,7,14,25,38,58,83,116,152,202,254,\ldots$. $\endgroup$ – lhf Dec 3 '14 at 0:47
  • $\begingroup$ The reason it should go as $n^2/6$ can be seen if you drop the floor function and replace the sums by integrals. $\endgroup$ – Mark Fischler Dec 3 '14 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.