I managed to find an efficient algorithm (polynomial time in $P$,$Q$ and $N$) for the following sum:
$$\sum_{i=0}^{N} \lfloor iP/Q \rfloor,$$
where $P,Q$ are relatively prime positive integers. When $N=Q-1$ it's fairly easy to get a simple closed form, and this is also well-known. The details of the general algorithm can be found here http://mathforum.org/library/drmath/view/73120.html. It is a very nice algorithm that resembles the standard GCD algorithm somewhat.
I'm trying to generalize this algorithm to sums of the following form:
$$\sum_{i=0}^{N} (i^{k0}) \cdot (\lfloor (iP/Q) \rfloor)^{k1},$$
where $k_0$, and $k_{1}$ are non-negative integers. Does anyone have any good ideas for this?
The algorithm doesn't have to be polynomial in $k_{0}$ and $k_{1}$, and algorithms for small values of $k_{0}$ and $k_{1}$ would also be interesting (such as $k_{0} = 0$). Obviously, $k_{1} = 0$ is not interesting.
Best Answer
It seems to me that at least for $k_0=0$ these sums always satisfy a linear recurrence. Maybe one can guess the general form of this recurrence. For example (using FriCAS):