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.

No comments:

Post a Comment