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_{23}2^{4}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_{1}, .., x_{n}}. The elements of R are consecutive integers such that x_{1} ≥ 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_{1} and x_{n} (this is an important visualization). The total distance between x_{1} and x_{n} is N-1. Hence, x_{1} = M – (N-1)/2 = S/N – (N-1)/2. If x_{1} 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_{1} = 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_{1} = 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^{m}P_{1}S_{2}, where P_{1} is the lowest odd prime factor of S and S_{2} 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^{m}P_{1}S_{2} *always* have a solution?

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

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

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

In the second case, where 2^{m+1} is less than P_{1}, 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_{1} is greater than 2^{m+1}, x_{1} is again positive. P_{1} and S_{2} are both odd, hence P_{1}S_{2} 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_{1} 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.

paulhartzerIt 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”.