Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 7 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|cite|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


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.