Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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.

share|improve this answer
    
... 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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.