Can a given number be written as a sum of two or more consecutive positive integers?

I need to write a method which takes in an int and returns true if the number can be written as a sum of two or more consecutive positive integers and false otherwise.

boolean IsSumOfConsecutiveInts(int num)

I figured out that all odd numbers (except the number 1) can be written as the sum of 2 consecutive positive integers:

return (num > 1 && num % 2 == 1);

but this doesn't account for numbers that can be written as the sum of more than 2 consecutive positive integers (such as 6 == 1 + 2 + 3).

How can I determine whether a number can be written as a sum of two or more consecutive positive integers?

Solution

These numbers are called Polite Numbers.

And, conveniently, the only numbers that aren't polite are the powers of 2.

So, that gives us 2 options. We can either determine that a number is polite, OR we can determine that it is not a power of 2.

I did both; the latter is easier (and more efficient).

This determines whether or not a number is polite:
```
boolean IsSumOfConsecutiveInts(int num)
{
    int sumOfFirstIIntegers = 3;
    for (int i = 2; sumOfFirstIIntegers <= num; i++)
    {
        if (i%2 == 0 ? (num%i == i/2) : (num%i == 0))
        {
            return true;
        }
        sumOfFirstIIntegers += i + 1;
    }
    return false;
}
```
This one is pretty hard to understand. It took me a while to come up with.

Basically, i is the number of consecutive integers that we are checking;

sumOfFirstIIntegers is equal to the sum of the first i integers, so that means that all the numbers that can be expressed as a sum of i consecutive integers are greater than or equal to sumOfFirstIIntegers.

The last part that deserves discussing is the boolean statement i%2 == 0 ? (num%i == i/2) : (num%i == 0). Let's look at some examples:
```
i    all sums of i consecutive positive integers
2    3, 5, 7, 9...
3    6, 9, 12, 15...
4    10, 14, 18, 22...
5    15, 20, 25, 30...
```
There are two cases, but in either case, we can express all possible numbers that are a sum of i consecutive integers pretty simply.
1. When i is even, num must be equal to (i * n) + (i / 2) where n is a non-negative integer. This can of course be written as num % i == i / 2.
2. When i is odd, num must be equal to i * n, where n is a non-negative integer. Which gives us our second condition num % i == 0.
In addition to these conditions, num can not be less than the sum of the first i positive integers. Hence, our for loop's conditional: sumOfFirstIIntegers <= num.
This determines whether a number is not a power of 2:
```
boolean IsSumOfConsecutiveInts(int num)
{
    return (num & (num - 1)) != 0;
}
```
This answer does a good job of explaining why this works.

Note that both of the above solutions have the same result, they are just different ways of thinking about the problem.