## 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.
```