UVa 10783: Odd Sum | MathBlog

UVa 10783: Odd Sum | MathBlog

We are given two integers  and , where . Our job is to compute the sum of the odd numbers between  and , inclusive. The bounds are so small that almost any solution will be fast enough. We can simply loop from  to  and sum up all odd numbers we find. Perhaps we will start with that, and then try to improve it as we go?

public static int OddSum(int a, int b) {

 

    int sum = 0;

 

    // go through each number from a to b

    for (int i = a; i <= b; i++) {

 

        // if the current number is odd

        if (i % 2 != 0) {

 

            // add it to the running sum

            sum += i;

        }

    }

 

    return sum;

}

public static int OddSum(int a, int b) {

 

    // if a is even

    if (a % 2 == 0) {

 

        // then the smallest odd integer we want is one greater than a

        a++;

    }

 

    int sum = 0;

 

    // go through every odd number from a to b

    for (int i = a; i <= b; i += 2) {

 

        // and add it to the running sum

        sum += i;

    }

 

    return sum;

}

Then we can express this problem as an arithmetic series. Basically we are looking at the n-term arithmetic series  where

One important thing however, is to figure out what , which we can do since we know what  is:

We are trying to find the sum of the terms up to and including , which means that we need to sum up the first  terms in the sequence. The sum of the first  terms in our sequence:

which is an arithmetic sequence series difference  (see proof).

public static int OddSum(int a, int b) {

    // if a is even

    if (a % 2 == 0) {

 

        // then the smallest odd integer we want is one greater than a

        a++;

    }

 

    // if b is even

    if (b % 2 == 0) {

 

        // then the largest odd integer we want is one less than b

        b--;

    }

 

    // find the index of b in the sequence

    int i = (b - a + 2) / 2;

 

    // calculate the sum of the first i numbers in the sequence

    return i * (a + (a + 2 * (i - 1))) / 2;

}

Read full article from UVa 10783: Odd Sum | MathBlog