0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do they have to be consecutive positive integers? $\endgroup$ – 6005 Sep 7 '15 at 16:13
  • $\begingroup$ If you are looking at integers rather than positive integers then $-n+1, -n+2 \dots -1, 0 ,1 \dots n-1, n$ will always sum to $n$ $\endgroup$ – Mark Bennet Sep 7 '15 at 16:13
  • $\begingroup$ Use the formula $$\sum_{j=a}^b j=\frac{(1+b-a)(a+b)}{2}$$ $\endgroup$ – Peter Sep 7 '15 at 16:17
  • $\begingroup$ I suspect you may suffer from integer overflow. $N$ can be as large as ten million, so with 32-bit integers, your computations overflow when $N$ is large enough. $\endgroup$ – Daniel Fischer Sep 7 '15 at 16:39
  • $\begingroup$ @DanielFischer For any given $N$, the upper bound of the result is also $N$. I'm fairly certain this is upper bound is correct, considering only one possible set could end in any $i$ where $1 <= i <= N$. 10,000,000 fits in all 32-bit integers. $\endgroup$ – user168210 Sep 7 '15 at 16:48
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am just noticing that our answers are extremely similar; I was just typing mine at the same time of yours, hope you don't mind if I leave it below. $\endgroup$ – Jack D'Aurizio Sep 7 '15 at 16:26
  • $\begingroup$ @JackD'Aurizio no problem, thanks for checking! $\endgroup$ – 6005 Sep 7 '15 at 16:27
  • $\begingroup$ To clarify, all the numbers must be integers, positive, and greater than zero. $\endgroup$ – user168210 Sep 7 '15 at 16:51
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the counts in the OEIS link are for decompositions as sums of positive integers - for example $2=-1+0+1+2$ is not counted, and of $3=1+2=0+1+2=-2+-1+0+1+2+3$ only $3=1+2$ is counted $\endgroup$ – Mark Bennet Sep 7 '15 at 16:45
  • $\begingroup$ @MarkBennet No, but they also aren't counted in the POJ problem. Else the decomposision $15 = (-14) + \ldots + 14 + 15$ would have been written there aswell. The description of the original problem on POJ makes it clear that only the sum of consecutive positive integers is meant. $\endgroup$ – Dominik Sep 7 '15 at 16:50
  • $\begingroup$ OK - but I referred to this because it is not completely clear in the OEIS link that this is what is being counted, and neither is it clear in the text of the question here. $\endgroup$ – Mark Bennet Sep 7 '15 at 16:55
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Two things. 1), even though $\endgroup$ – user168210 Sep 7 '15 at 16:54
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy