How to sum sequence of floors numbers?

Question

How can I sum the following sequence:

⌊n∕2⌋ + ⌊n+1∕2⌋ + ⌊n+2∕2⌋ + ...... + (n-1)

What I think is discard the floor and sum what inside each floor !! This is just a guess.

Give me any hint or general formula that helps me to sum them

Thanks

Answer 1

Assuming n is even, then floor(n/2) == floor((n+1)/2). And floor((n+2)/2) == floor(n/2) + 1.

The other piece in the puzzle is the expression for the sum of an arithmetic sequence, which can be found here.

Answer 2

Since you're asking on a programming Q&A site, I must assume you want a computational answer. Here goes...

int sum = 0;
for (int j=0; j<n-1; ++j) {
    sum += (n+j)/2;
}

The int will automatically truncate to the floor.

The less smart ass answer is this. Let n = 2k. Then the sum becomes

k + k + k+1 + k+1 + ... + 2k-1 + 2k-1 = 2(k + k+1 + ... + 2k-1)

and you can use the formula

1 + 2 + ... + a = a(a+1)/2

with a bit of algebra to finish it off.

Answer 3

for the arbitrary range 1..20 you could do:

sum = (1..20).inject{|sum, n| sum + (n/2.0).floor}

and of course you could use any range. This example is in Ruby, but you could do something similar in many languages - the algorithm is the same.

Answer 4

As long as you're not asking for a clever algorithm or optimizations, the simplest approach I can think of is good old trusty looping. In C#, one way to do that would look something like this:

namespace Practice
{
    using System;

    public class SequenceAggregator
    {
        public double FirstElement
        {
            get;
            set;
        }

        public int Length
        {
            get;
            set;
        }

        public double Calculate()
        {
            double sum = 0;

            for (var i = FirstElement; i < FirstElement + Length; i++)
            {
                sum += Math.Floor(i / 2);
                Console.WriteLine("i={0}, floor(i/2)={1}, sum={1}", 
                                  i, Math.Floor(i/2), sum);
            }

            return sum;
        }
    }
}

And you can use this class in the following way:

namespace Practice
{
    using System;

    class Program
    {
        static void Main(string[] args)
        {
            SequenceAggregator a = new SequenceAggregator();
            a.FirstElement = 1;
            a.Length = 3;
            Console.WriteLine("Sum:{0}", a.Calculate());
        }
    }
}