# Algorithm for summing certain sums involving the floor function

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.

-
BTW Compare Dedekind sums: en.wikipedia.org/wiki/Dedekind_sum – Dan Piponi Jan 4 '11 at 23:11
When you say that your algorithm runs in polynomial time, I presume you mean that its complexity is polynomial in the size of its inputs, i.e. $\log P$, $\log Q$, and $\log N$. – AVS Jan 5 '11 at 10:22

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]

-

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