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.

For example, 6 has a max of 3 distinct integers excluding 0 that can form its sum (1,2,3). I can't think of any property that that I could exploit, even the recursions do not have good base cases.

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

The smallest integer that can be written as the sum of $n$ distinct positive integers is $$\sum_{k=1}^nk=\frac{n(n+1)}2=\binom{n+1}2\;.$$

If $$\binom{n+1}2\le m<\binom{n+2}2\;,\tag{1}$$ then $m$ can be written as the sum of $n$ distinct positive integers but not of $n+1$ distinct positive integers. Specifically, let $d=\sum_{k=1}^nk-m\ge 0$; then

$$m=\sum_{k=1}^{n-1}k+(n+d)\;.$$

To find $n$ directly from $m$, note that $(1)$ can be rewritten as $$n(n+1)\le 2m<(n+1)(n+2)\;,$$ or as $$\left(n+\frac12\right)^2\le 2m+\frac14<\left(n+\frac32\right)^2$$ after adding $\frac14$ and completing the squares. Now take square roots to get $$n+\frac12\le\sqrt{2m+\frac14}<n+\frac32$$ and subtract $\frac12$: $$n\le\sqrt{2m+\frac14}-\frac12<n+1\;,$$ or, more simply, $$n=\left\lfloor\sqrt{2m+\frac14}-\frac12\right\rfloor\;.$$

share|improve this answer
    
Awesome. It could be asking too much but is there a way to find out the numbers themselves? Like 6 -> (1,2,3) –  kunjan kshetri Mar 22 '12 at 13:36
    
@Kunjan: Yes. Once you have $n$, calculate $d=m-\binom{n+1}2$, then write $m$ as $1+2+3+\dots+(n-1)+(n+d)$. This won’t in general be the only possible breakdown; as long as $d>0$, there will always be others. –  Brian M. Scott Mar 22 '12 at 20:44
add comment

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.