Summation of Floor Function SeriesDate: 01/12/2009 at 09:11:36 From: Ivan Subject: Formula for the sum of [ ] Hello! Is there any formula for the sum [p/q] + [2p/q] + [3p/q] + ... + [np/q] (p, q, n are natural numbers)? For example, [3/7] + [2*3/7] + [3*3/7] + [4*3/7] + [5*3/7] = 0 + 0 + 1 + 1 + 2 = 4 I can't find a correct formula for any natural p and q. I suspect that it does not exist. Maybe there is an algorithm for calculating such sums? It can be proved that if n = q - 1 then [p/q] + [2p/q] + [3p/q] + ... + [(q-1)p/q] = (p-1)(q-1)/2. Date: 01/14/2009 at 14:12:28 From: Doctor Vogler Subject: Re: Formula for the sum of [ ] Hi Ivan, Thanks for writing to Dr. Math. That's a very interesting question. I think that your suspicion is correct that there is not a closed-form formula for the general sum. Fortunately, however, there is an efficient algorithm for computing the sum. By way of notation, I will write your sum as sum(k=1, n, [kp/q]). Your formula for n=q-1 can be generalized to reduce n by any multiple of q, as in sum(k=1, n, [kp/q]) = pt(n+1) - t(pqt + p + q - 1)/2 + sum(k=1, n-tq, [kp/q]) You'll notice that when t=1 and n=q-1 (so that the last sum is zero), you get your formula. Actually, your formula and this formula both depend on p and q having no factors in common (so that p/q is a fraction in reduced form). Of course, it's also easy to reduce p by an integer multiple of q, and then we get sum(k=1, n, [kp/q]) = tn(n+1)/2 + sum(k=1, n, [k(p-qt)/q]). But when n and p are both smaller than q, then it's harder to figure out what to do. But here is one idea: We can count the number of times that [kp/q] = m for each number m. It turns out that [kp/q] = m when m <= kp/q < m+1 or mq/p <= k < (m+1)q/p so that if both of those numbers are smaller than n, then this happens for {(m+1)q/p} - {mq/p} different values of k, where I write {x} to mean x rounded *up* to the nearest integer (which is also sometimes called the ceiling function), in parallel to your notation [x] to mean x rounded *down* to the nearest integer (which is also sometimes called the floor function). (It turns out that these satisfy {x} = -[-x] for all x. Also, if x is an integer, then {x} = [x] = x, but if x is not an integer, then {x} = [x] + 1.) The last (biggest) m that will appear is m = [np/q], which happens for n+1 - {mq/p} different values of k. So that means that sum(k=1, n, [kp/q]) = m(n + 1 - {mq/p}) + sum(k=1, m-1, k({(k+1)q/p} - {kq/p})). By looking at how this sum nearly telescopes, we can rewrite it as sum(k=1, n, [kp/q]) = m(n + 1) - sum(k=1, m, {kq/p}). If we additionally assume that mq/p is never an integer, then this is the same as sum(k=1, n, [kp/q]) = mn - sum(k=1, m, [kq/p]). Now you might ask whether we have actually made any progress. We've changed one sum that we don't know how to evaluate efficiently for another sum that looks exactly the same. But here's the clincher: The new sum changed around some numbers, allowing us to repeat all three formulas and continue to make progress. So when we put it all together, we get the following very efficient algorithm: Input: Positive integers n, p, q Output: s = sum(k=1, n, [kp/q]) Algorithm: t = GCD(p, q) p = p/t q = q/t s = 0 z = 1 while (q > 0) and (n > 0) (point A) t = [p/q] s = s + ztn(n+1)/2 p = p - qt (point B) t = [n/q] s = s + zpt(n+1) - zt(pqt + p + q - 1)/2 n = n - qt (point C) t = [np/q] s = s + ztn n = t swap p and q (e.g. t = p, p = q, q = t) z = -z It can be proven that this algorithm will finish in polynomial time, which basically means that a computer could use this to evaluate sums very quickly even if the input numbers are hundreds or thousands of digits long. In fact, this algorithm is comparable to the Euclidean Algorithm for computing the GCD of two numbers. The reason the algorithm works is that we initially force GCD(p, q) = 1, so that our formula for reducing n by a multiple of q will work. Then subtracting qt from p and swapping p and q do not change this fact. Then at points A, B, and C, the sum we are looking for is s + z*sum(k=1, n, [kp/q]). Going from A to B, we use the formula for reducing p by a multiple of q. Going from B to C, we use the formula for reducing n by a multiple of q. Then going from C to A, we use the last formula that I demonstrated. The reason that kq/p is never an integer at that point is that kq/p is never an integer at point C (for k <= t) is that when we went from B to C, we caused that n < q, and then k <= t <= np/q < qp/q = p and since k is less than p, p cannot be a factor of k. And then since q and p have no factors in common, p cannot be a factor of kq, so kq/p is not an integer, and we can use the formula with [] rather than the one with {}. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 01/15/2009 at 15:57:49 From: Ivan Subject: Formula for the sum of [ ] Thanks for your answer. But I do not understand clearly how did you get this formula: sum(k=1, n, [kp/q]) = pt(n+1) - t(pqt + p + q - 1)/2 + sum(k=1, n-tq, [kp/q]) Could you help me? Date: 01/17/2009 at 01:38:56 From: Doctor Vogler Subject: Re: Formula for the sum of [ ] Hi Ivan, Oh, sure! That's basically just the formula that you already gave me, just applied to the end of the sum and t times. You had said that sum(k=1, q-1, [kp/q]) = (p - 1)(q - 1)/2. Of course, this would also apply to sum(k=0, q-1, [kp/q]) = (p - 1)(q - 1)/2. The trick is to use this to sum sum(k=m, m+q-1, [kp/q]). Well, kp/q is going to have all of the same fractional parts; we just move some of them from the beginning of the sum to the end. That is the same as saying that sum(k=0, q-1, kp/q - [kp/q]) = sum(k=m, m+q-1, kp/q - [kp/q]). Does that make sense? But then the first parts, the sum of kp/q is just a regular arithmetic series, so (p/q)q(q-1)/2 - sum(k=0, q-1, [kp/q]) = (p/q)q(2m+q-1)/2 - sum(k=m, m+q-1, [kp/q]). And then we substitute your formula and get sum(k=m, m+q-1, [kp/q]) = p(2m+q-1)/2 - p(q-1)/2 + (p-1)(q-1)/2 = pm + (p-1)(q-1)/2. Therefore sum(k=1, n, [kp/q]) = sum(k=1, n-q, [kp/q]) + p(n-q+1) + (p-1)(q-1)/2. Now we just iterate this, or prove by induction on t that sum(k=1, n, [kp/q]) = pt(n+1) - t(pqt + p + q - 1)/2 + sum(k=1, n-tq, [kp/q]). We've just proven it for t=1. The inductive step only requires expanding the sum on the right side, sum(k=1, n-q, [kp/q]), by the same formula, and simplifying. Does that make sense? - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 01/26/2009 at 07:47:24 From: Ivan Subject: Formula for the sum of [ ] Hi, Doctor Vogler, First of all, thank you for your quick response. I am really interested in how to calculate such sums. What do you think, can we find an algorithm for computing sum(k=1, n, [sqrt(kp/q])), for example? We can count the number of times that [sqrt(kp/q)] = m for each number m, can we? [sqrt(kp/q)] = m when m <= sqrt(kp/q) < m+1 or m^2 q/p <= k < (m+1)^2 q/p and m:=1 to [sqrt(np/q)] Maybe, however, there is a more efficient algorithm? I wonder whether there are any methods of summation of functions? Once again, thank you very much. Date: 01/26/2009 at 12:50:40 From: Doctor Vogler Subject: Re: Formula for the sum of [ ] Hi Ivan, That's a good question. Certainly if p/q isn't very large (roughly if p/q < n), then a better way to sum the series sum(k=1, n, [sqrt(kp/q)]) would be to do the conversion you described, which results in N(n+1) - sum(m=1, N, {qm^2/p}), where N = [sqrt(np/q)] and you'll recall that I was using {x} to mean the "ceiling" function (round up). You might even prefer this method when p/q is a little larger than n, just because squaring is easier to do than square-rooting. Then we can also reduce q by a multiple of p. But I can't think of any other transformations that would allow us to keep simplifying like we did in the other sum. Maybe if we could figure out the value of sum(m=1, p-1, [qm^2/p]) then we could use this to reduce N by a multiple of p. Even then, however, I don't think it would be productive to convert back into a sum of square roots again. So I don't think you can do better than summing [sqrt(np/q)] terms (which is not polynomial time, but maybe it's good enough for your purposes). - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/