1. Overview
In this tutorial, we’ll explore how to determine whether a given number can be expressed as the sum of two or more consecutive integers.
We’ll begin by understanding the mathematical principles behind consecutive integer sequences and how their properties can simplify our problem-solving process. Then, we’ll implement two approaches: a brute-force method and an optimized approach.
2. Mathematical Background
To see how these decompositions work in practice, let’s consider a few examples:
-
9 = 2 + 3 + 4 or 4 + 5
-
15 = 4 + 5 + 6
-
10 = 1 + 2 + 3 + 4
-
7 = 3 + 4
By contrast, we don’t find two or more consecutive positive integers that add up to 8.
Let’s begin by revisiting a result that directly leads to the criterion for identifying powers of two.
Every positive integer a can be written as a sum of two or more consecutive positive integers precisely when there exist integers k ≥ 1 and n ≥ 1 such that:
a = (n+1)*k + (n*(n+1))/2
The formula comes from the standard “sum of the first n integers” shifted to start at k:
n*(n+1)/2
Multiplying by 2 on both sides, we get:
2a = (n+1) *2k + n*(n+1) = (n+1) * (2k + n)
With this equation in hand, we can now prove why the powers of two fail to decompose and why every other positive integer succeeds.
2.1. Powers of Two Fail the Test
Let’s suppose a is a power of two. Then 2a is also a power of two, so its only positive divisors are powers of two. But in any factorization:
2a = (n+1) * (2k+n)
Regardless of whether n is even or odd, the two factors n+1 and 2k+n always have opposite parity, so they can’t be powers of two.
Moreover, to avoid the trivial cases (using only one summand), we require n ≥ 1 and k > 0. The only way two powers of two multiply to another power of two with opposite parity would force either n+1=1 (so n=0) or 2k+n=1 (so k=0), both of which violate our constraints. Hence, no power of two can be written as a sum of two or more consecutive positive integers.
2.2. Every Other Integer Works
Conversely, any integer a that isn’t a power of two has at least one odd divisor d > 1:
d=2m+1, a=d*q
For some integer q, the sequence:
(a/d - m), (a/d - m + 1), ..., (a/d + m)
Consists of d consecutive integers whose sum is exactly a. Even if a/d − m ≤ 0, one can shift the sequence by dropping negative terms and adding positive ones symmetrically to maintain the sum (or choose a different odd divisor), guaranteeing a valid representation.
Thus, all positive integers except powers of two can be expressed as the sum of two or more consecutive positive integers.
3. Brute-Force Approach
We’ll start with a straightforward method: try every possible sequence length until we either find a valid sum or exhaust our options. This approach is easy to understand and works well for moderate values of n:
@Test
void whenIsSumOfConsecutiveUsingBruteForce_thenItsTrue() {
int n = 15;
boolean isSumOfConsecutive = false;
for (int k = 2; (k * (k - 1)) / 2 < n; k++) {
int diff = n - k * (k - 1) / 2;
if (diff % k == 0 && diff / k > 0) {
isSumOfConsecutive = true;
break;
}
}
assertTrue(isSumOfConsecutive);
}
We loop over each possible length k, compute whether the remaining amount divides evenly, and check that the starting number stays positive. We return true if we find a match; otherwise, we return false after all lengths fail.
4. Optimized Approach
We can reduce the check to a single bitwise operation. If a positive integer n isn’t a power of two, it can be written as the sum of two or more consecutive integers. Otherwise, it can’t:
@Test
void whenIsSumOfConsecutiveUsingBitwise_thenReturnsTrue() {
int n = 15;
boolean result = (n > 0) && ((n & (n - 1)) != 0);
assertTrue(result);
}
We return true when n is positive and fails the power of two tests. This runs in constant time and space, making it extremely efficient even for very large n.
5. Conclusion
In this article, we demonstrated that any positive integer can be expressed as the sum of two or more consecutive positive integers precisely when it isn’t a power of two.
Our brute-force approach methodically tested each possible sequence length, making it straightforward and reliable for moderate values of n. By contrast, the optimized bitwise check gives an O(1) solution that instantly identifies non-powers of two, making it ideal for very large inputs.
As always, the source code is available over on GitHub.
