Sums of Positive Consecutive Integers: Proof

In my previous post, I tackled this problem:

Try to express positive integers in terms of the sum of two or more consecutive positive integers. For instance, 3 = 1+2, 9 = 2+3+4, and so on. For which numbers 1 to 25 is it possible to do this?

I incorrectly concluded that there were no solutions for numbers of the form P₂₃2⁴S (that is, a prime number greater than 19 times a power of 2 greater than 8). Even though I checked it several times, I apparently limited the Excel VBA to series of 20 or fewer numbers, and numbers of the “exceptional” form require series of more than that. For instance, the shortest series for 368 (23•16) involves 23 numbers.

Once I was done licking my pride wounds, having devoted so much energy to my non-discovery of a bizarre pattern, I dug back into it: Why would 368 require 23 numbers, while 184 (23•8) had a shorter solution? And is there a way to determine whether a given integer S has a solution of a given length N?

I’ll answer the second question first. I’ll also try to formalize a bit better.

Let R be the set {x₁, .., x_n}. The elements of R are consecutive integers such that x₁ ≥ 1. Let N be the number of elements in R, and let S be the sum of the elements in R. Finally, let M be the average of R; hence, M = S/N and S = N • M.

Note that if we set all the elements of R along a number line, M would be the midpoint between x₁ and x_n (this is an important visualization). The total distance between x₁ and x_n is N-1. Hence, x₁ = M – (N-1)/2 = S/N – (N-1)/2. If x₁ is a positive integer, then R represents a solution for S with N elements.

Let’s try it. For instance, we want to know if there is a 3-element solution for 15. x₁ = 15/3 – (3-1)/2 = 5 – 1 = 4 ⇒ R = {4, 5, 6} ⇒ N = 4 + 5 + 6 = 15. Success! Let’s say we want to know if there’s a 7-element solution for 21. x₁ = 21/7 – (7-1)/2 = 3 – 3 = 0. R = {0, 1, 2, 3, 4, 5, 6} does have a S of 21, but these numbers are not all positive integers.

So now we have a process for seeing if there’s an R of size N that solves S, and if so, determining the first element:

R having |R|=N solves S iff \(\frac{S}{N} – \frac{N-1}{2}\) is a positive integer.

This is what we need to prove that S has a solution R (of some |R|>1) iff S cannot be expressed as 2^m.

It is the case either that S = 2^m or that S = 2^mP₁S₂, where P₁ is the lowest odd prime factor of S and S₂ is the product of any remaining prime factors. For instance, 14 = 2 • 7 • 1, 35 = 1 • 5 • 7, and 308 = 4 • 7 • 11.

I did prove that S = 2^m has no solutions in the edit on my previous post. Here it is again (pasted verbatim):

If we start at 1, we see this pattern:
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
This is a fairly well-known series: 1, 3, 6, 10, 15…: \(\sum\limits_{i=1}^N i \). It can be rewritten simply as \(\frac{N(N+1)}{2}\).

If we increase any single element in the set by X, we have to increase every element in the set by X; for instance, adding 5 to 1 + 2 + 3 + 4 would make it 6 + 7 + 8 + 9. Hence, the sum of any set of consecutive positive integers can be expressed as: \[S = \frac{N(N+1)}{2} + XN \\ = N \cdot (\frac{N+1}{2} + X) \\  = N \cdot\frac{N+1 + 2X}{2} \]

Let’s say that N is odd. S in that case must clearly have an odd factor, and hence cannot be a power of 2 (which only has even factors). Let’s say that N is even. Since N is even and 2X is even, N + 1 + 2X must be odd. S again has to have an odd factor. Hence, it cannot be a power of 2. In other words, since S must have at least one odd factor, it cannot be a power of 2.

This proves that S = 2^m has no solutions. Does S = 2^mP₁S₂ always have a solution?

The answer is yes. We have two cases to consider: Either 2^m+1 is greater than P₁, or it’s less than it. They can’t be equal since the first is even and the second, odd.

Recall that x₁ = S/N – (N-1)/2 is always a solution, and rewrite it to x₁ = (2S/N – N + 1)/2.

In the first case, where 2^m+1 is greater than P₁, let’s try N = P₁ as a solution. This yields: \[ x_1 = (\frac{2S}{P_1} – P_1 + 1)/2 \\ S = 2^m\cdot P_1 \cdot S_2 \implies \\ x_1 = (\frac{2 \cdot 2^m \cdot P_1 \cdot S_2}{P_1} – P_1 + 1)/2 \\ = (2^{m+1} \cdot S_2 – P_1 + 1)/2 \]

Since 2^m+1 is greater than P₁, x₁ is positive. An even number minus an odd plus an odd equals an even, and half an even number is an integer. Hence, x₁ is a solution to S.

In the second case, where 2^m+1 is less than P₁, let’s try N = 2^m+1 as a solution. This yields: \[ x_1 = (\frac{2S}{2^{m+1}} – 2^{m+1} + 1)/2 \\ S = 2^m\cdot P_1 \cdot S_2 \implies \\ x_1 = (\frac{2 \cdot 2^m \cdot P_1 \cdot S_2}{2^{m+1}} – 2^{m+1} + 1)/2 \\ = (P_1 \cdot S_2 – 2^{m+1} + 1)/2 \]

Since P₁ is greater than 2^m+1, x₁ is again positive. P₁ and S₂ are both odd, hence P₁S₂ is odd. An odd number minus an even plus an odd is an even number, and half of an even number is an integer. Hence, x₁ is a solution to S.

This proves that S has a solution R for all values that are not powers of 2; it also illustrates why 23•16 requires 23 numbers (23 < 32) while 23•8 requires only 16 (16 < 23). As we would expect, 592 (37•16) requires 32 numbers, not 37 (3+4+…+34); 1184 (37•32) requires 37 (14+15+…+50). All of this proves the original hypothesis: A positive integer S is equal to the sum of consecutive positive integers iff it has odd prime factors.