Algorithm for summing certain sums involving the floor function

Question

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 Link. 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.

Answer 1

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):

(1) -> )expose RECOP
(1) -> floorsum(p, q, k, n) == reduce(+, [floor(i*p/q)^k for i in 0..n])
(2) -> guessEq(p, q, k) == (N := 50; while empty?(e := guessPRec([floorsum(13, 17, k, n) for n in 0..N], safety==100, maxDegree==0)) repeat N := N+1; getEq first e = 0)
(3) -> guessEq(13,17,0)
   (3)  - f(n + 1) + f(n) + 1= 0
(4) -> guessEq(13,17,1)
   (4)  - f(n + 18) + f(n + 17) + f(n + 1) - f(n) + 13= 0
(5) -> guessEq(13,17,2)
   (5)
   - f(n + 35) + f(n + 34) + 2f(n + 18) - 2f(n + 17) - f(n + 1) + f(n) + 338= 0
(6) -> guessEq(13,17,3)
   (6)
     - f(n + 52) + f(n + 51) + 3f(n + 35) - 3f(n + 34) - 3f(n + 18) + 3f(n + 17)
   + 
     f(n + 1) - f(n) + 13182
     =
     0
(7) -> guessEq(13,17,4)
   (7)
     - f(n + 69) + f(n + 68) + 4f(n + 52) - 4f(n + 51) - 6f(n + 35) + 6f(n + 34)
   + 
     4f(n + 18) - 4f(n + 17) - f(n + 1) + f(n) + 685464
     =
     0
(9) -> guessEq(13,17,5)
   (9)
     - f(n + 86) + f(n + 85) + 5f(n + 69) - 5f(n + 68) - 10f(n + 52)
   + 
     10f(n + 51) + 10f(n + 35) - 10f(n + 34) - 5f(n + 18) + 5f(n + 17)
   + 
     f(n + 1) - f(n) + 44555160
     =
     0
(12) -> guessPRec [1,13,338,13182,685464,44555160]
   (12)  [[f(n): - f(n + 1) + (13n + 13)f(n)= 0,f(0)= 1]]
(13) -> guessPRec [1,18,35,52,69,86]
   (13)  [17n + 1]

Answer 2

General hints to generalization:

• don't generalize too many things at once (e.g. just stick with $k_0 = 0$ for now as noted)
• start with trying to solve with small nontrivial constants, e.g. $k_1 = 2$. That'll probably be complex enough.

Specific hints to this problem

• let $N = Q-1$ or $N = m Q - 1$. By the link you gave, all sorts of things are easier (telescoping, switching quantifiers, fewer 'inscrutables') when you go complete cycles.