Floor sum

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
User avatar
Posts: 2
Joined: Fri Nov 29, 2019 10:53 am

Floor sum

Post 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.
Posts: 71
Joined: Mon Oct 06, 2008 6:14 pm

Re: Floor sum

Post 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.
Post Reply