Associated Topics || Dr. Math Home || Search Dr. Math

### Summation of Floor Function Series

```Date: 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),
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 {}.

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/
```
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search