Partitions into Consecutive Integers

For any positive integer N, let f(N) denote the number of ways in
which n can be expressed as the sum of consecutive positive integers.
For example, since 9 can be expressed as 2+3+4 and as 4+5 and as 9,
we have f(9)=3.

The sum of the integers from 1 to n is n(n+1)/2, so we're looking 
for the number of ways in which a given integer N can be expressed 
in the form 
                  N = n(n+1)/2 - m(m+1)/2                   (1)

for a positive integer n and non-negative integer m.  Solving this 
for m gives
                        ____________________
                  -1 + / 1 - 4[2N - n(n+1)]
          m   =   ---------------------------
                                2

which implies that the quantity inside the square root must be a 
square integer.  Thus there is an integer u such that

           4n^2 + 4n + 1 - 8N - u^2  =  0

Clearly u must be odd.  Solving this for n gives
                             _________
                       -1 + / 8N + u^2
                n  =   ----------------
                                2

Again, this requires that the quantity inside the square root is a 
square integer, so we have an integer v such that

            8N  =  v^2 - u^2  =  (v-u)(v+u)

and since u is odd, v must also be odd.  Thus we can write this in 
the form
               2N  =  [(v-u)/2] [(v+u)/2]

So we are looking for ways of factoring 2N into two factors, A=(v-u)/2 
and B=(v+u)/2 with odd integers u,v.  We have v=A+B and u=B-A, so A 
and B must have opposite parity, i.e., one is odd and one is even.  
Thus, the integers A,B give a solution if and only if 2N = AB and one 
of A,B is odd and the other is even.  Clearly this occurs for any odd 
divisor d of N, which let's us take A=d and B=2N/d (or vice versa, 
which ever give B > A).  Consequently, the number of ways of expressing 
N as a sum of consecutive positive integers is equal to the number of 
odd divisors of N.

For example, there are three odd divisors of N=9, namely 1, 3, and 9, 
so we have f(9) = 3, corresponding to the three solutions

          A   B     v   u     n   m       expression
         --- ---   --- ---   --- ---     -------------
          1   18    19  17     9  8        9
          3    6     9   3     4  1        2+3+4
          2    9    11   7     5  3        4+5
      
Incidentally, if we let F(N) denote the number of ways of expressing 
N  as the sum of consecutive integers, without requiring that they be
positive integers, then clearly F(N) = 2f(N), because for any sum of
consecutive integers extending from -m to n the total is again given
by equation (1), and for each solution that ranges from m+1 to n
there corresponds an equivalent solution ranging from -m to n.

Return to MathPages Main Menu