### Sum of consecutive positive integers

A while back, I proposed the following math problem to my co-workers who have become interested in my little academic challenges.

Determine the number of ways "2009" can be expressed as a sum of consecutive positive integers.

Below, you'll find the solution I derived from scratch.

Observe: Consider the sum of integers between 1 and 10, with removing the first term in each set.
 (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10) (2 + 3 + 4 + 5) + 6 + (7 + 8 + 9 + 10) (3 + 4 + 5 + 6) + (7 + 8 + 9 + 10) (4 + 5 + 6) + 7 + (8 + 9 + 10) (5 + 6 + 7) + (8 + 9 + 10) (6 + 7) + 8 + (9 + 10) (7 + 8) + (9 + 10) (8) + 9 + (10) 9 + 10 = 55 = 54 = 52 = 49 = 45 = 40 = 34 = 27 = 19 = 11 x 5 = 12 x 4 + 6 = 13 x 4 = 14 x 3 + 7 = 15 x 3 = 16 x 2 + 8 = 17 x 2 = 18 x 1 + 9 = 19 x 1 [10 terms] [9 terms] [8 terms] [7 terms] [6 terms] [5 terms] [4 terms] [3 terms] [2 terms]

Generalize: Based on the observations above, we can generalize some relationships by substituting some variables:
• F = first term
• L = last term
• N = number of terms
• A = average of terms
• S = sum of all terms
Derive: We can derive relationships based on the ten examples above.
1. A = (F + L) / 2 (somewhat obvious, but important)
2. L = F + N - 1 (arguably just as obvious, as long as you remember the 1)
3. S (N even) = (F + L) x (N / 2) (sum with even number of terms)
4. S (N odd) = (F + L) x [(N - 1) / 2) + A (sum with odd number of terms)
Reduce: The sum S seems to have a dual relationship, but it's worth closer inspection. Let's substitute equations #1 and #2 into equations #3 and #4.

S (N even) = (F + L) x (N / 2) = (2F + N - 1)(N / 2) (easy enough)

 S (N odd) = (F + L) x [(N - 1) / 2) + A = (2F + N - 1) x [(N - 1) / 2] + (2F + N - 1) / 2 = (2F + N - 1)(N / 2) - (2F + N - 1) / 2 + (2F + N - 1) / 2 = (2F + N - 1)(N / 2)

Deduce: Based on our findings, we can make the following deductions:
• The sum S is always the value (2F + N - 1)(N / 2) and can be determined from just the value of the first term and the total number of terms.
• We know S = 2009, so by multiplying both sides by 2: 4018 = N(2F + N - 1).
• These unknown values N and (2F + N - 1) both divide the number of 4018.
• If we let X = 2F + N - 1, we can express 4018 = N(2F + N - 1) = NX.
• We can solve for F in terms of X and N by shifting around: F = (X + 1 - N) / 2.
• Therefore, if we know the values of N and X, we can determine the value of F (the first term).
Factor: Obviously we need to determine the factors of 4018. My preferred method is prime factorization:

4018 = 2 x 2009 = 2 x 7 x 287 = 2 x 7 x 7 x 41. Thus:
4018 = 1 x 4018, 2 x 2009, 7 x 574, 14 x 287, 41 x 98, 49 x 82.

These pairs are our values of N and X. And as deduced above, we can determine F based on X.

Evaluate: We must consider all cases of N and X that yield an acceptable (i.e. nonnegative) value for F.
• N = 1, X = 4018: F = (4018 + 1 - 1) / 2 = 4018 / 1 = 4018 = F
• N = 2, X = 2009: F = (2009 + 1 - 2) / 2 = 2008 / 2 = 1004 = F
• N = 7, 574: F = (574 + 1 - 7) / 2 = 568 / 2 = 284 = F
• N = 14, X = 287: F = (287 + 1 - 14) / 2 = 274 / 2 = 137 = F
• N = 41, X = 98: F = (98 + 1 - 41) / 2 = 58 / 2 = 29 = F
• N = 49, X = 82: F = (92 + 1 - 49) / 2 = 34 / 2 = 17 = F
• N = 82, X = 49: F = (49 + 1 - 82) / 2 = -32 / 2 = -16 < 0 (not valid, neither are the rest)
Conclude: From the above results, we can conclude that there are 5 sums (6, if you include the trivial one-term case).
• 2009 = 2009 (1 term)
• 2009 = 1004 + 1005 (2 terms)
• 2009 = 284 + 285 + ... + 289 + 290 (7 terms)
• 2009 = 137 + 138 + ... + 149 + 150 (14 terms)
• 2009 = 29 + 30 + ... + 68 + 69 (41 terms)
• 2009 = 17 + 18 + ... + 64 + 65 (49 terms)
For those of you who are more into math than myself, you probably thought this was a walk the park. But for everyone else, I hope this walkthrough proved both accessible and elegant.