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

Question

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.

Answer 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.

Answer 2

Assume that $N$ is the sum of $k$ consecutive integers: $$ N = a+(a+1)+\ldots+(a+k-1).\tag{1}$$ It follows that: $$ N = ka + \frac{k(k-1)}{2}\tag{2}$$ that is equivalent to: $$ 2N=k(2a+k-1) \tag{3}$$ so there is a solution iff $k$ is a divisor of $2N$ and $\frac{2N}{k}$ has the opposite parity of $k$.

That gives a naive algorithm with running time $O(\sqrt{N})$: just test every number in $[1,\sqrt{2N}]$ to be a divisor of $2N$ (that accounts also for the complementary divisor $\frac{2N}{k}$), then check if the previous condition holds. The problem has the same complexity of computing the number of divisors of $N$.

You may save a little time by computing first the greatest power of two that divides $N$. You may check that if $N=2^h$, there are just two ways of writing $N$ as a sum of consecutive integers, corresponding to the decompositions $2N=1\cdot 2^{h+1}$ and $2N=2^{h+1}\cdot 1$.

Answer 3

Either the sum of consecutive integers will contain an odd number of integers or an even number. Let's deal with the odd case first - and let the middle number be $n$ with the total being $N$ and $2r+1$ consecutive integers involved. Then the sum is $$N=(n-r)+(n-r+1)+\dots +(n-1)+n+(n+1)+\dots +(n+r)=(2r+1)n$$

Each odd factor $2r+1$ of $N$ gives one such decomposition, and you will be able to work out the condition for the lowest of the numbers to be positive, if necessary.

For an even decomposition with $2r$ terms we have

$$N=(n-r+1)+\dots +(n-1)+n+(n+1)+\dots +(n+r-1)+(n+r)=(2r-1)n+(n+r)=r(2n+1)$$ and this gives a decomposition into an even number of consecutive integers for each odd factor of $N$ taken as $2n+1$.

---

Now suppose we have a decomposition of $N\gt 0$ which includes zero. If the least non-positive integer in the decomposition is $-r$, then the $2r+1$ integers $-r\le n\le r$ sum to zero, and can be deleted to give a decomposition containing only positive terms.

On the other hand, if the decomposition contains only positive terms with the least of these being $r+1$ then the $2r+1$ integers $-r\le n\le r$ can be added to the sequence to give a decomposition which includes zero.

So this pairing tells us that precisely half of the above decompositions are wholly positive - one for each odd factor.

Careful analysis will show that the pairing matches the odd and even decompositions related to the same odd factor (it is clear from the comments above that the paired decompositions differ in the parity of the number of terms).

Deduct $1$ if the trivial decomposition is not included.

Answer 4

The other answers already answered how to calculate the number more efficiently, but since you've asked for a list of values I will provide one. If you don't count a "sum" of $1$ number as a sum, the wanted value is called politeness of the number and can be found in OEIS/A069283.