# Sum of Natural Number Ranges?

Given a positive integer $n$, some positive integers $x$ can be represented as follows:

$$1 \le i \le j \le n$$ $$x = \sum_{k=i}^{j}k$$

Given $n$ and $x$ determine if it can be represented as the above sum (if $\exists{i,j}$), and if so determine the $i$ and $j$ such that the sum has the smallest number of terms. (minimize $j-i$)

I am not sure how to approach this. Clearly closing the sum gives:

$$x = {j^2 + j - i^2 + i \over 2}$$

But I'm not sure how to check if there are integer solutions, and if there are to find the one with smallest $j-i$.

-

A start: Note that $$2x=j^2+j-i^2+i=(j+i)(j-i+1).$$ The two numbers $j+i$ and $j-i$ have the same parity (both are even or both are odd). So we must express $2x$ as a product of two numbers of different parities.

-
... and so there is a potential solution for every odd divisor of $x$. One trivial solution would be $i=j=x$ (provided that $x \le n$) corresponding to the divisor $1$. – Henry Jun 26 '12 at 6:45

Some pointers:

Factor the numerator of your fraction to get

$$x = {j^2 + j - i^2 + i \over 2}=\frac{(j-i+1)(j+i)}2\;.$$

Let $d=j-i+1$ and $s=j+i$; you have $2x=ds$, and you want to minimize $d$. Moreover, you have $d+s=2j+1$, so $d$ and $s$ are of opposite parity: one is odd, and one is even.

Now suppose that $ds$ is any factorization of $2x$ such that $d$ and $s$ have opposite parity. Then $d+s-1$ is even, so you can set $j=\frac12(d+s-1)$, and so is $s-d+1$, so you can set $i=\frac12(s-d+1)$. I leave it to you to check that if you do this, you really will have $x=\sum_{k=i}^jk$.

Does $2x$ always have such a factorization? Yes: even if $x$ is a power of $2$, it can be written as $1\cdot(2x)$. The question is whether it has one that yields $i$ and $j$ in the required range. Note that it’s enough to get $j\le n$, i.e., $d+s-1\le 2n$, or $d+s\le 2n+1$.

-
Note that $n$ is fixed, though, so there's still a bit left to do. – Zev Chonoles Jun 26 '12 at 5:42
@Zev: I didn’t intend to imply that it was the whole answer, but I should make that explicit. – Brian M. Scott Jun 26 '12 at 5:45