Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 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.
share|improve this 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):

(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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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