7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ BTW Compare Dedekind sums: en.wikipedia.org/wiki/Dedekind_sum $\endgroup$
    – Dan Piponi
    Jan 4, 2011 at 23:11
  • $\begingroup$ 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$. $\endgroup$
    – AVS
    Jan 5, 2011 at 10:22

2 Answers 2

2
$\begingroup$

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]
$\endgroup$
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.