Is there a list of the number of sets of consecutive integers that sum to n?

I'm trying to solve this problem on POJ and I thought that I had it. Since I can't figure out what's wrong with my code, I'd like to test it against a huge list of correct answers. This will make my code much easier to debug.

If you don't want to go to the page linked above, or figure out what exactly the problem is asking, here's a concise version:

Given a positive integer $N$, determine $x$, the number of sets of consecutive positive integers that sum to $N$.

For example, suppose $N = 15$. Then $x = 4$, since, by brute force, the only possible solutions are

$\{15\}$, $\{7, 8\}$, $\{4, 5, 6\}$, and $\{1, 2, 3, 4, 5\}$

My algorithm runs in $O(n)$ time, although it uses the $sqrt(x)$ function, which is quite expensive. Here's some pseudocode:

input n

if n = 1 or n = 2:
    print 1
    exit

count = 1
for i = n / 2 + 1; i * (i + 1) / 2 >= n; i -= 1:
    j = sqrt(i * (i + 1) - 2 * n)
    if i * (i + 1) - j * (j + 1) = 2 * n or 
    i * (i + 1) - (j + 1) * (j + 2) = 2 * n:
        count += 1

print count
exit

Here's some English explaining the loop:

Start with the greatest number, $i$, of a possible set. Disregarding the trivial set $\{N\}$, $i$ clearly cannot be greater than $N / 2$. (Suppose $i > N / 2$ and $i < N$. Then $i + (i + 1) > N$ and $i + (i - 1)$ may or may not be equal to $N$.) Since $i$ cannot be greater than $N/2$, start with $i = N/2$ as the upper bound of $i$. To test each possible set, loop $i$ from this upper bound down until $i (i + 1) / 2 < N$. Clearly, if the sum all positive integers from $1$ to $i$ is less than $N$, then no set of consecutive integers, whose greatest number is $i$, could sum to $N$. This establishes the lower bound of $i$.

To test if a set could end in $i$, I use the following mathematics:

Let

$$S(x) = \sum_{j=1}^{x} j$$

Starting with a set composed solely of $i$, add a set which most closely sums (including $i$) to $N$. Mathematically,

$$N = i + S(i - 1) - S(x)$$

$S(i - 1) - S(x)$ will generate some set of consecutive integers whose greatest number is $i - 1$ and whose least number is between $1$ and $i - 1$, inclusively. To rewrite,

$$N = i + \frac{(i-1)i}{2} - \frac{x(x + 1)}{2}$$ $$2N = 2i + i(i - 1) - x(x + 1)$$ $$2N = i(i + 1) - x(x + 1)$$

Therefore, $i(i + 1) - 2N = x(x+1)$ for some $x \in R$. If $x \in N$, then a solution has been found, generating the set of consecutive integers from $x + 1$ to $i$, inclusive. To quickly determine whether $x \in N$, I square-root $i (i + 1) - 2N$ and round down to some integer $t$. I plug $t$ back in to the equation for $x$, and check to see if it works. If $i(i + 1) - 2N \not = t(t+1)$ then I increment $t$ by one and check again. If neither of the cases work, then a valid set could not possibly have a greatest value of $i$, so I decrement $i$, continuing the loop.

My algorithm has worked for hundreds of test cases, but when I submit, POJ gives me WRONG ANSWER. This is why I'd like to have a list of correct answers to compare against my program.

Solution 1:

Why your algorithm doesn't work: You need to allow the set of consecutive integers to be negative. For instance, you say in your code that $1$ and $2$ have only one solution. But each of them have two solutions: $$ 1 = 1 \;;\; 1 = 0 + 1 \\ 2 = 2 \;;\; 2 = -1 + 0 + 1 + 2 $$ In fact, the answer will always end up being an even number, as seen in the formula at the end of this post.

An explicit formula: If $j$ consecutive integers sum to $n$, and the first is $i$, then \begin{align*} &(i) + (i+1) + (i+2) + \cdots + (i + j-1) = n \\ &\implies \frac{(2i+j-1)j}{2} = n \\ &\implies 2n = (2i+j-1)j. \tag{1} \end{align*} Conversely, if $jk = 2n$ for some positive integer $j$ and some integer $k$, with $k, j$ different modulo $2$, then setting $2i+j-1 = k$ we get a solution from (1).

Therefore, your answer is the number of ways to factor $2n = jk$ where $j > 0$ and $j,k$ differ mod $2$. $j > 0$ implies $k > 0$, so the factors must both be positive.

Write $2n = 2^d n'$ with $n'$ odd, $d \ge 1$. Then your answer will be $$ \boxed{2 \sigma_0(n'),} $$ where $\sigma_0$ counts the number of positive integer divisors of $n'$. You multiply by $2$ because we can either choose to put the $2^d$ into $j$, or into $k$, but we can't split it between them.