Is there a list of the number of sets of consecutive integers that sum to n?
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.
Related videos on Youtube
Admin
Updated on December 11, 2021Comments
-
Admin almost 2 years
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.-
6005 about 8 yearsDo they have to be consecutive positive integers?
-
Mark Bennet about 8 yearsIf 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$
-
Peter about 8 yearsUse the formula $$\sum_{j=a}^b j=\frac{(1+b-a)(a+b)}{2}$$
-
Daniel Fischer about 8 yearsI 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.
-
Admin about 8 years@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.
-
Daniel Fischer about 8 yearsBut your loop starts with setting $i = \bigl\lfloor \frac{n}{2}\bigr\rfloor + 1$, and the loop condition checks whether $i\cdot (i+1)/2 \geqslant n$. The results of intermediate computations (can) exceed 32-bit range. If you're using 64-bit integers, it's not that, but if you use 32-bit integers, overflow is likely to happen, since probably there are some larger $N$ among the inputs.
-
Admin about 8 years@DanielFischer Good point! I overlooked this.
-
Admin about 8 years@DanielFischer I just submitted with
unsigned long long
and I still gotWRONG ANSWER
. -
Daniel Fischer about 8 yearsOkay, then you probably have a bug in the algorithm.
-
-
Jack D'Aurizio about 8 yearsI 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.
-
6005 about 8 years@JackD'Aurizio no problem, thanks for checking!
-
Mark Bennet about 8 yearsI 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
-
Dominik about 8 years@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.
-
Admin about 8 yearsTo clarify, all the numbers must be integers, positive, and greater than zero.
-
Admin about 8 yearsTwo things. 1), even though
-
Mark Bennet about 8 yearsOK - 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.