The integer 30 can be written as a sum of consecutive positive integers in three ways:
30 = 9+10+11 = 6+7+8+9 = 4+5+6+7+8.

Find the smallest positive integer which can be written as a sum of consecutive positive integers in 12 ways.

(In reply to How to thread these by Gamer)

Some guy named Riley has it figured out very simply -- see

http://www.perldiscuss.com/article.php?id=2211&group=perl.golf

The "weird" cases are where the divisor is small and is repeated a large number of times, for example 1 repeated n times. 1 repeated n times comes out finally as floor(n/2) + (floor(n/2)+1). To take a very simple example, consider n=15. The divisors are 1,3,5,15 so we expect 4 partitions into consecutive parts. We have

15x1=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=

       =-6-5-4-3-2-1+0+1+2+3+4+5+6+7+8=7+8,

 5x3=3+3+3+3+3=1+2+3+4+5,

 3x5=5+5+5=4+5+6, and

1x15=15

This method works for any odd divisor of the given number, with the particular odd divisor being the number of times the complementary factor (which may be even or odd) is repeated. If, after modifying the terms about the middle term to get a sum of consecutive numbers, negative terms result, these negative terms are always cancelled by equal positive terms and the net result is a sum of an even number of positive terms.

Does this method give all possible breakdowns of a given positive integer as a sum of consecutive positive integers? Yes it does.  An even number of consecutive positive terms, say (k+1)+...+(k+2*m) sums to [2*(k+m)+1]*m, an odd positive multiple of m, and is equal to the sum of the 2*(k+m)+1 consecutive terms from -k to k+2*m.  And an odd number of consecutive positive terms, say (k+1)+...+(k+2*m+1), sums to (2*m+1)*(k+m+1), an odd positive multiple of k+m+1. Thus any sum of consecutive positive integers is always an odd positive multiple of some other positive integer and its representation as that sum of those particular consecutive positive integers will be obtained as one of the representations that Riley's method provides.

Edited on July 4, 2004, 8:57 pm

Posted by Richard on 2004-06-29 17:56:15