Many numbers can be broken into a staircase of consecutive positive integers. The challenge is to identify the one family that never allows such a decomposition.
The Hidden Sum
Riddle statement
Some numbers can be written as the sum of two or more consecutive positive integers.
For example:
- 9 = 4 + 5
- 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
- 21 = 10 + 11 = 6 + 7 + 8
But some numbers cannot be written in this way at all.
Which family of numbers always resists?
Show solution
Solution
The numbers that resist are exactly the powers of 2.
1. Why a power of 2 cannot occur
Suppose n is the sum of k consecutive positive integers, starting at a, with k ≥ 2:
n = a + (a + 1) + ··· + (a + k − 1)
Using the formula for an arithmetic sum:
n = k(2a + k − 1)/2.
If k is odd, then 2a + k − 1 is even. Therefore (2a + k − 1)/2 is an integer, and k is an odd divisor of n greater than 1.
If k is even, we can write:
n = (k/2)(2a + k − 1).
The second factor is odd and, because a ≥ 1 and k ≥ 2, it is greater than 1. Every representable number therefore has an odd divisor greater than 1.
A power of 2 has no odd divisor greater than 1, so it cannot have such a representation.
2. How to construct a representation for every other number
Let n be a number that is not a power of 2. Write it as:
n = 2ˢm, where m is odd and m > 1.
Because m is odd and 2ˢ⁺¹ is even, equality is impossible, so exactly one of the following cases applies.
Case A: m < 2ˢ⁺¹.
Take m consecutive integers centered at 2ˢ. The first is:
2ˢ − (m − 1)/2.
Since m < 2ˢ⁺¹ and m is odd, m ≤ 2ˢ⁺¹ − 1, so this first term is at least 1.
The average is 2ˢ, and therefore the sum of the m terms is:
m · 2ˢ = n.
Case B: m > 2ˢ⁺¹.
Take 2ˢ⁺¹ consecutive integers beginning with:
a = (m − 2ˢ⁺¹ + 1)/2.
Because m is odd, a is an integer; and because m > 2ˢ⁺¹, a is at least 1. The average of these terms is m/2, so their sum is:
2ˢ⁺¹ · m/2 = 2ˢm = n.
Thus every number that is not a power of 2 has at least one representation as a sum of two or more consecutive positive integers.