# Find all pairs (i, j), such that i + (i+1) + (i+2) + … + j = n

We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$

Clearly we can try all possible pairs in $O(N^2)$, but that is pretty slow. Here is my observation.

We already know that the sum of numbers from $1$ to $n$ equals $\frac{n\cdot(n+1)}{2}$. Using simple math we can show that the sum of the numbers in the range from $i$ to $j$ equals $\frac{(j-i+1)\cdot(i+j)}{2}$. If we fix number $i$ using this formula we can find $j$, and check if it is positive integer, but this is $O(N)$, can we go faster?

Another algorithm:

Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$. Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+r-1)/2$. Check whether $i,j$ are positive. If they are, output this pair $i,j$. Do this for each way of expressing $2n$ as the product $2n=r \times s$.

How do you find all factorizations of $2n$ into two integers? First factor $2n$ into a product of prime powers, say

$$2n = \prod p_i^{e_i}.$$

Next, for each $c_i$ with $0 \le c_i \le e_i$, you can let $r = \prod p_i^{c_i}$ and $s = \prod p_i^{e_i-c_i}$. So in this way you can enumerate all such factorizations. There will be $\prod (1+e_i)$ of them.

The running time for this is significantly faster than $O(n)$. In the worst case the number of such factorizations can be no larger than $O(n^{1/2})$, so the worst-case running time of this method is $O(n^{1/2})$ -- already a significant speedup over Hendrik Jan's elegant answer. Even better, in the average case, the number of such factorizations is far smaller than $n$, exponentially smaller, making this much faster. Often, the dominant cost will be the cost to factor $2n$, which can be done in subexponential time using standard algorithms.

• Since one factor is ≤ n^(1/2), the number of factorisations cannot be more than O (n^(1/2)). – gnasher729 Oct 14 '17 at 20:51
• Excellent point, @gnasher729, thank you! – D.W. Oct 15 '17 at 1:11

Set $i$ and $j$ to $1$. Set $\mathrm{sum}$ to $0$.

Repeat:

If $\mathrm{sum} = n$ we have a pair, if $\mathrm{sum} < n$ increment $j$ and adjust $\mathrm{sum}$, if $\mathrm{sum} > n$ increment $i$ and adjust $\mathrm{sum}$.

• As I can see, this is $O(N)$, can we go anything faster ? – someone12321 Oct 14 '17 at 16:03
• This actually works for the more general 'finding $a_i+a_{i+1}+\cdots+a_j=n$' on positive arrays. – Willard Zhan Oct 14 '17 at 18:26
• @WillardZhan You are right of course, so perhaps we can use the fact that $a_i=i$ in a clever way? – Hendrik Jan Oct 14 '17 at 20:40