Divide an integer into the sum of consecutive positive numbers

Today I am trying to solve an classical problem:

For any $n\in \Bbb{N}^+$, If it can be represent as the sum of consecutive positive numbers, find out them.

For example:

$$15 = 1+2+3+4+5$$ $$15=4+5+6$$ $$15=7+8$$

And I have an ugly method, its time complexity is: $O(n^2)$. I use two for loop to exhaustion all possibilities.

for(int i=1;i<n;i++)
{
for(int j=i;j<n;j++)
{
sum+=j;
if(sum==n)
{   //print out the answer
for(int l=i;l<=j;l++)
{
cout << l << "+ ";
}
cout << endl;
break;
}
}
sum = 0;
}


I think there may be exist a more effective solution, But I am failed until now. Please help me.

for i from 1 to n
{
for j from i to n
{
sum <- sum + j
if sum equal n
{
print the result
}
}
sum <- 0
}

-
Do you want all partitions? Do you want one partition? What have you tried? What research have you done? There's lots written on this problem. Are you aware that $p(n)$, the number of partitions, grows exponentially with $n$, so there is no hope for a $O(n^2)$ time solution? P.S. Please replace your code with pseudocode readable by any computer scientist (even one who doesn't know C++). This site focuses on algorithms, not code/implementations. – D.W. May 9 '14 at 15:58
@D.W. The number of partitions into consecutive numbers is at most linear, since for each smallest number in the partition, there can be at most 1 sequence. – FrankW May 9 '14 at 17:58
Ahh, thank you, I missed that they had to be consecutive. (My other comments still apply: the author needs to show us what she has tried, where she got stuck, and try to identify a more narrowly crafted question, so this isn't just a problem dump; and to replace code with pseudocode.) – D.W. May 9 '14 at 18:27
@D.W. thanks for your advise. I have add the pseudocode. My first try is brute force. Now I have some other way to solve it. I will post it later. thanks very much. – Laura May 24 '14 at 2:12

Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum_{i=1}^m i = \frac{(m+1)m}{2}$, $$\sum_{i=a+1}^b i = \sum_{i=1}^b i - \sum_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \frac{(b-a)(b+a+1)}{2}.$$ Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we want $x,y$ to have different parities (this is only a restriction if $n$ is even) and $y \geq x+1$. Also, $b \neq a+1$ corresponds to $x \neq 1$.

For example, for $n = 15$ we have $2n = 30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$. These correspond to the following pairs $(a,b)$: $$(6,8),(3,6),(0,5).$$ These, in turn, correspond to the representations $$15 = 7+8 = 4+5+6 = 1+2+3+4+5.$$

This leads to an $O(n)$ algorithm (in the appropriate computation model). I'll let you work out the remaining details.

-

Here's a hint: if $n$ can be represented as the sum of $2k+1$ consecutive integers, and if the middle of those consecutive integers is $m$, then what can you say about the relationship between $n$, $k$, and $m$? Now, given $n$, can you determine whether it is expressible as the sum of an odd number of consecutive integers?

-

You can replace your second "for" loop with binary search, since you can calculate sum of arithmetical progression by formula. I mean traverse all possible values of lengths and try to find starting value by binary search, it replaces second $N$ with $log(N)$

I found my old $O(NlogN)$ code where $N$ is the maximal length of representation $1+2+...+N$. It searches the lenght of this representation.

int ans = 1, n; cin >> n;
for(int len = 2; len <= 32000; len++)
{
int l = 1, r = n/2;
while (l <= r)
{
int mid = (l+r)/2;
__int64 cur_sum = (2*mid + len - 1) * 1LL * len / 2;
if (cur_sum == n) { ans = len; break; }
if (cur_sum < n) l = mid+1;
else r = mid-1;
}
}
cout << ans;


I'm not sure it works ok on all cases, currently I'm writing binserach differently, but the idea is clear I think.

-
I recommend that you replace the code in your answer with pseudocode, to ensure that it will be understandable by everyone, and focus on the concepts rather than the implementation. Our focus is on algorithms, not code or implementations. – D.W. May 9 '14 at 20:28

Here's a $O(\sqrt n)$ algorithm. We want to find all length-$k$ expressions for which $$n=a+(a+1)+(a+2)+\cdots+(a+(k-1))$$ Rearranging terms, we require $$n=\sum_{i=0}^{k-1}(a+i) = \sum_{i=0}^{k-1}a+\sum_{i=0}^{k-1}i=ka+\frac{k(k-1)}{2}$$ and so we must have $$n=k\left(\frac{2a+k-1}{2}\right)$$ for some $a$ and $k$. If $k$ is even we require $$n=\left(\frac{k}{2}\right)(2a+k-1)$$ and so $n$ must be divisible by $k/2$. If $k$ is odd, we'll have $2a+k-1$ even, so $n$ must be divisible by $k$.

That means that the possible solutions will only be those for which $k$ is odd and $k\mid n$ or $k$ is even and $(k/2)\mid n$. Now that we know that we're looking only for divisors of $n$, we'll have candidate pairs $k$ and $n/k$ for those $k\le \sqrt{n}$ if $k$ is odd and $k\le 2\sqrt{n}$ if $n$ is even. That means we can find all solutions by checking at most only the $k\le2\sqrt{n}$. Since each check involves nothing more than a constant number of steps, we can find all the solutions in time $O(\sqrt{n})$.

Let's look at your example, with $n=15$:

1. ($k=1$). We have $15 = 1\cdot(2a+1-1)/2$ so $a=15$, giving the sum 15=15. The other solution will be when $k=15$, giving an impossible solution.
2. ($k=2$). We have $15=(2/2)(2a+1)$ and so $a=7$, giving the solution 15=7+8. The companion solution, where $k=15/1$ is impossible, again.
3. ($k=3$). We have $15=3\cdot(2a+2)/2$, so $a=4$, giving another solution 15=4+5+6. The companion solution, when $k=15/3=5$ gives $a=1$, which yields the solution 15=1+2+3+4+5.
4. ($k=4$). Since $4/2=2$ doesn't divide 15, there is no possible solution.
5. ($k=5$). Since $5>\sqrt{15}$ we can stop looking at odd candidates.
6. ($k=6$). $6/2$ divides 15, but we've already considered that solution. There are no further even numbers to consider, and so we stop trying, having found all the possible solutions.
-