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 P2324S (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 {x1, .., xn}. The elements of R are consecutive integers such that x1 ≥ 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 x1 and xn (this is an important visualization). The total distance between x1 and xn is N-1. Hence, x1 = M – (N-1)/2 = S/N – (N-1)/2. If x1 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. x1 = 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. x1 = 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 2m.

It is the case either that S = 2m or that S = 2mP1S2, where P1 is the lowest odd prime factor of S and S2 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 = 2m 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 = 2m has no solutions. Does S = 2mP1S2 always have a solution?

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

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

In the first case, where 2m+1 is greater than P1, let’s try N = P1 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 2m+1 is greater than P1, x1 is positive. An even number minus an odd plus an odd equals an even, and half an even number is an integer. Hence, x1 is a solution to S.

In the second case, where 2m+1 is less than P1, let’s try N = 2m+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 P1 is greater than 2m+1, x1 is again positive. P1 and S2 are both odd, hence P1S2 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, x1 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.

1 Comment

  1. paulhartzer

    It occurred to me later that this provides a direct proof all odd numbers have N=2 solutions: All odd numbers are of the form 2^0•P_1•S_2. Since 2^(0+1) = 2 will always be lower than P_1, N=2^(0+1)=2 will always provide a solution.

    Also, if we generalize P_1 to be 1 if there are no odd factors available in S, the proof still works but requires us to allow N=1 as a possible size of R (which is to say, any integer can be expressed in terms of the sum of consecutive integers if we allow “sum of consecutive” to refer to a single digit–something that makes sense in strict mathematics but not in conventional English). If N = 1, then R = S/N – (N-1)/2 = S/1 – (1-1)/2 = S; S is tautologically a positive integer, and so |R|=1 always provides a solution to S.

    This suggests that, in terms of this particular problem, numbers of the form 2^N•P_1•S_2 where P_1 and S_2 both equal 1 (that is, powers of two) are deficient (in the colloquial but not mathematical sense of the term): The key qualifier is that a positive integer has to have at least one odd prime factor, not that it can’t be a power of 2, in order to have an R that solves it.

    Pedagogically (since this was the context in which this problem came up), though, it would likely be easier for the typical high school student to understand “powers of two” as a constraint than “odd prime factor”.

    Reply

Leave a Reply to paulhartzer Cancel reply

Your email address will not be published. Required fields are marked *