0

I was stumbled upon a math problem that I can't seem to solve efficiently.

I was asked to create a group of a consecutive number that sums up to a whole number, e.g.

4,3,2,1 = 10
4,3,2 = 9
5,4,3,2 = 14

constraints:
  • the group of numbers doesn't need to reach to 0 or 1
  • the group of numbers needs to be consecutive
  • the group of numbers has to be smallest size (if there are more than one groups)

Is there a math logic that can help me to get the number grouping efficiently, without having to create all the possible combinations first?

Asaf Karagila
  • 393,674
Prima Aulia Gusta
  • 1
  • Presumably you want to exclude the trivial representation ($n=n$). This paper provides some useful results. – lulu Jun 20 '17 at 11:14
  • Related: https://math.stackexchange.com/questions/1936782/some-numbers-are-sums-of-consecutive-numbers-which-numbers-can-be-written-in-mo/1936839#1936839 – Ivan Neretin Jun 20 '17 at 11:25

1 Answers1

0

If $n=m+(m+1)+\ldots+(m+k)=(k+1)m+\frac{k(k+1)}2$ then $2n=(k+1)(2m+k)$.

Write $n=2^ru$ with $u$ odd. As $k+1\not\equiv 2m+k\pmod 2$, we must have either $k+1=u, 2m+k=2^{r+1}$ or $k+1=2^{r+1},2m+k=u$. The first leads to a valid solution only if $u>1$ (i.e., if $n$ is not a power of $2$), the other leads to a valid solution only if $r\ge1$ (i.e., if $n$ is even).

Thus we find as result:

  • If $n$ is a power of $2$, then $n$ is the sum of $2n$ consecutive integers starting at $1-n$
  • If $n$ is odd, then $n$ is the sum of $n$ consecutive integers starting at $\frac{3-n}2$
  • In all other cases, we can write $n=2^ru$ with $r\ge 1$ and $u\ge 3$ odd. Then we can write $n$ as either the sum of $u$ consecutive integers starting from $2^r-\frac{u-1}2$, or as the sum of $2^{r+1}$ consecutive integers starting from $\frac{u+1}2-2^r$. (Pick the shorter one)
Hagen von Eitzen
  • 374,180