Find all series of consecutive positive integers whose sum is exactly 10,000.
__________________________________

What if we don't require the consecutive integers to (all) be positive?

Referencing a comment on an earlier and somewhat similar problem... here.  The method is unclear and needs improvement.

Now to repeat what I said but more clearly, and adding a bit so it applies to this problem, and the general case.

Take any set of consecutive integers.  Call its length L.  Call the average of the set M.  If L is odd, M is the middle numbert.  If L is even, M is a multiple of 1/2 between the middle numbers.  The sum of the set is LM.

So for our number N (which, in this case, is 10,000) to equal LM, N/L must equal M, and M must be an integer if L is odd and an integer + .5 if L is even.

It would seem that the number of sets of consecutive integer  is related to the number of divisors of N.  It is, but only certain divisors.  There is a set of consecutive integers that sums to N for every odd divisor of N.  There are also as many even Ls that work as there are odd Ls.

Before explaining the previous statement, let me explain how to find the number of divisors.  Take the prime factorization of N.  Let's say that it is 2^3*3^5*7^2.  First only consider odd divisors of N.  The divisors can have any integer between 0 and 5 3s in its prime factorization.  It can also have any integer between 0 and 3 7s in its prime factorization.  It must have 0 2s in its prime factorization.  So the number of divisors is (5+1)(2+1)(1), or 18.  The number of divisors is equal to the product of 1 more than each of the exponents in the prime factorization (excluding the factor 2 if the divisors are odd.)

Back to the earlier statement at the end of 2 paragraphs above, there are actually two proofs of this that I thought up.

Proof 1: The even divisors aren't really divisors of N, but are  divisors of 2*N, because if L is even, then N/L is a fraction multiple of 1/2.  This in mind, consider 10,000.  Its prime factorization is 2^4*5^4.  The even numbers should not be able to divide this, but they should be able to divide into 2^5*5^4.  Therefore, they are multiples of 2^5.

We can now say that each L that makes a sequence that sums to N, either has none of N's 2 factors, or all of 2N's 2 factors.  Since it can only be one or the other, there is in fact an even L corresponding to every odd L.
____________________________________________

Proof 2:  Each sequence of positive integers is either even or odd.  For every positive sequence, there is a partly negative sequence.  Say the sequence goes from 4 to 81.  The sequence from -3 to 81 has the same sum because -3 through 3 sum to zero.  You can add a zero sum sequence to every positive sequence.  Since this zero sum sequence has an odd number of terms (including 0), the negative sequence is the opposite parity length of the positive sequence.  So, including both positive and negative, the number of even length sequences is equal to the number of odd length sequences.
____________________________________________

In proof 2, I also proved that if only positive sequences are allowed, then there are only half of the sequences that sum to N.

So to sum up... The number of consecutive integer sequences that sum to N is double the product of 1 more than each of the exponents in the prime factorization of N, excluding the 2 factors.  The actual sequences are determined by dividing N by L and making that the average of the sequence and L the length.

For 10,000, the prime factorization is 2^4*5^4, so there are 2*(4+1), or 10 sequences that work.  The different Ls are 1,5,25,125,625,32,160,800,4000, and 20000.  I have reason to believe the lowest 5 Ls, 1,5,25,32, and 125, are the ones that result in positive sequences.

Posted by Tristan on 2004-07-30 21:42:09