Take the 2-minute tour ×

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

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


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

Your Answer


