Page 1 of 1

Floor sum

Posted: Fri Nov 29, 2019 11:37 am
by bole79
I've noticed Graham, Knuth (Concrete Mathematics, 2nd ed., p. 86) show how to do sum(floor(sqrt(k)), 0 <= k < n). Did anybody try and tackle sum(floor(sqrt(k (r / 2 - k))), 0 < k < r / 2)? This would actually solve a particular PE problem in closed form.

Re: Floor sum

Posted: Wed May 27, 2020 7:55 pm
by pjt33
If there is a solution along similar lines to the one for $\lfloor \sqrt{k} \rfloor$ then it's a polynomial in $n$ and $\lfloor \sqrt{n} \rfloor$. Asymptotically the solution is $\Theta(n^2)$, so there are only 9 coefficients to determine. Pick 9 values of $n$, perform Gaussian elimination to get the coefficients, and test to see whether it works for all $n$ up to some small bound.

Hint: it doesn't.

This isn't really surprising when you look at the integrals. $\int_0^n \sqrt{x} \textrm{d}x = \tfrac23 n^{3/2}$ has a nice rational coefficient, but $\int_0^n \sqrt{x(n-x)} \textrm{d}x = \tfrac\pi 8 n^2$ doesn't.