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

1,240

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.

Share:
1,240

Related videos on Youtube

Admin
Author by

Admin

Updated on December 11, 2021

Comments

  • Admin
    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
      6005 about 8 years
      Do they have to be consecutive positive integers?
    • Mark Bennet
      Mark Bennet about 8 years
      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$
    • Peter
      Peter about 8 years
      Use the formula $$\sum_{j=a}^b j=\frac{(1+b-a)(a+b)}{2}$$
    • Daniel Fischer
      Daniel Fischer about 8 years
      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.
    • Admin
      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
      Daniel Fischer about 8 years
      But 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
      Admin about 8 years
      @DanielFischer Good point! I overlooked this.
    • Admin
      Admin about 8 years
      @DanielFischer I just submitted with unsigned long long and I still got WRONG ANSWER.
    • Daniel Fischer
      Daniel Fischer about 8 years
      Okay, then you probably have a bug in the algorithm.
  • Jack D'Aurizio
    Jack D'Aurizio about 8 years
    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.
  • 6005
    6005 about 8 years
    @JackD'Aurizio no problem, thanks for checking!
  • Mark Bennet
    Mark Bennet about 8 years
    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
  • Dominik
    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
    Admin about 8 years
    To clarify, all the numbers must be integers, positive, and greater than zero.
  • Admin
    Admin about 8 years
    Two things. 1), even though
  • Mark Bennet
    Mark Bennet about 8 years
    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.