3
$\begingroup$

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

2 Answers 2

3

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.

  • 0
    ... 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$.2012-06-26
1

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

  • 0
    @Zev: I didn’t intend to imply that it was the whole answer, but I should make that explicit.2012-06-26