5
$\begingroup$

I was wondering if there a way to figure out the number of ways to express an integer by adding up consecutive natural numbers.

For example for $N=3$ there is one way to express it
$1+2 = 3$

I have no idea where to start so any help would be appreciated

$\endgroup$
  • $\begingroup$ Would for any odd number $N$ the sum of the two integers that bracket half that number count as one solution? Or as two? $\endgroup$ – hardmath Jan 12 '15 at 4:20
  • 1
    $\begingroup$ Consecutive integers or consecutive naturals? $\endgroup$ – Milo Brandt Jan 12 '15 at 4:23
  • $\begingroup$ @Meelo sorry, I meant consecutive natural numbers. I'll edit it in the question $\endgroup$ – lllll Jan 12 '15 at 4:25
  • 1
    $\begingroup$ The sum of the natural numbers from $a$ to $b$ inclusive is $\frac{(a+b)(a-b+1)}{2}$. $\endgroup$ – Thomas Andrews Jan 12 '15 at 4:25
  • $\begingroup$ See OEIS sequence A001227, oeis.org/A001227 $\endgroup$ – Robert Israel Jan 12 '15 at 4:27
13
$\begingroup$

The sum of the integers from $1$ to $n$ is $\dfrac{n(n+1)}{2}$. Hence, the sum of the integers from $m+1$ to $n$ is simply $\dfrac{n(n+1)}{2}-\dfrac{m(m+1)}{2}$. So, if the sum of the integers from $m+1$ to $n$ is $N$, then

$\dfrac{n(n+1)}{2}-\dfrac{m(m+1)}{2} = N$

$(n^2+n) - (m^2+m) = 2N$

$(n-m)(n+m+1) = 2N$

Hence, $n-m$ and $n+m+1$ are complementary factors of $2N$. Clearly, $n-m$ is smaller than $n+m+1$, and since $(n+m+1)-(n-m) = 2m+1$, the factors have opposite pairity.

For any $f_1$ and $f_2$ such that $2N = f_1f_2$, $f_1 > f_2$ and $f_1$, $f_2$ have opposite parity, we can solve $n+m+1 = f_1$ and $n-m = f_2$ to get $n = \dfrac{f_1+f_2-1}{2}$ and $m = \dfrac{f_1-f_2-1}{2}$.

Therefore, the number of ways to write $N = (m+1)+(m+2)+\cdots+(n-1)+n$ is simply the number of ways to factor $2N$ into two distinct positive integers with opposite parity.

Suppose $2N = 2^{k_0+1}p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$ where $p_1,p_2,\ldots,p_r$ are distinct odd primes. There are $(k_1+1)(k_2+1)\cdots(k_r+1)$ ways to divide the odd primes between $f_1$ and $f_2$. There are $2$ ways to give all $2$'s to one of the factors $f_1$, $f_2$. However, we need to divide by $2$ since this overcounts cases in which $f_1 < f_2$. Also, we need to subtract out the one trivial solution $n = N$ and $m = N-1$. This leaves us with $(k_1+1)(k_2+1)\cdots(k_r+1)-1$ ways to factor $2N$ into two distinct positive integers with opposite parity.

Therefore, if $N$ has prime factorization $N = 2^{k_0}p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$, then there are $(k_1+1)(k_2+1)\cdots(k_r+1)-1$ ways to write $N$ as the sum of two or more consecutive positive integers.

$\endgroup$
  • 2
    $\begingroup$ Which is equal to the number of odd factors of $N$ bigger than $1$. $\endgroup$ – Thomas Andrews Jan 12 '15 at 4:37
  • $\begingroup$ Isn't it turning polynomial problem into subexponential? $\endgroup$ – Imaskar says Reinstate Monica Sep 3 '18 at 9:47
  • $\begingroup$ A brute force approach to this problem is polynomial in $N$, while computing the prime factorization of $N$ is sub-exponential in $\ln N$ (not subexponential in $N$ itself). $\endgroup$ – JimmyK4542 Sep 3 '18 at 16:35
-1
$\begingroup$

SUm of the first n consecutive numbers.

n*(n+1)/2. ex: what is the sum of first 4 consecutive no's: with out formula: 1+2+3+4 = 10 with formula: 4*(4+1)/2 = 20/2 = 10

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.