Given an integer $N$, I have to find the number of ways by which $N $can be expressed as sum of consecutive integers. The rule is to use at least two integers.
For example, $N = 15$ has three solutions, $(1+2+3+4+5), (4+5+6), (7+8)$ .
I am trying to make important observations to solve this problem . Surprisingly I could not find any way to solve this problem.
Guys, can you help me in this regard?
Best Answer
Let $N = 2^{\alpha_2} 3^{\alpha_3} 5^{\alpha_5} \ldots q^{\alpha_q}$, where $q$ is the largest prime dividing $N$.
We want $N = a + (a+1) + (a+2) + (a+3) + \cdots b = \frac{(b-a+1)(a+b)}{2}$, where $a,b \in \mathbb{N}$
So we need to find $a$ and $b$ such that $(b-a+1)(a+b) = 2^{(\alpha_2 + 1)} 3^{\alpha_3} 5^{\alpha_5} \ldots q^{\alpha_q}$.
Now note that $(a+b)$ and $(b-a+1)$ are of opposite parity.
So one of them has to be odd. Further $(a+b)>(b-a+1)$ since $a \in \mathbb{N}$.
Assume that $(a+b)$ is even. So $(b-a+1)$ is odd.
Hence $$(a+b) = 2^{(\alpha_2 + 1)} 3^{\beta_3} 5^{\beta_5} \ldots q^{\beta_q}$$ $$(b-a+1) = 3^{\alpha_3-\beta_3} 5^{\alpha_5-\beta_5} \ldots q^{\alpha_q-\beta_q}$$ where $0 \leq \beta_p \leq \alpha_p$ and $(a+b) > (b-a+1)$
Now assume that $(a+b)$ is odd. So $(b-a+1)$ is even.
Hence $$(a+b) = 3^{\beta_3} 5^{\beta_5} \ldots q^{\beta_q}$$ $$(b-a+1) = 2^{(\alpha_2 + 1)} 3^{\alpha_3-\beta_3} 5^{\alpha_5-\beta_5} \ldots q^{\alpha_q-\beta_q}$$ where $0 \leq \beta_p \leq \alpha_p$ and $(a+b) > (b-a+1)$
If we relax the fact that it has to be written as a sum of consecutive natural numbers, and assume that the consecutive numbers belong to integers then we get $$2 \times (1+\alpha_3) \times (1+\alpha_5) \times (1+\alpha_7) \cdots \times (1+\alpha_q)$$
Note that the above also acts as a trivial upper bound if it has to be written as a sum of consecutive natural numbers. This upper bound is obtained by violating the constraint $(a+b) > (b-a+1)$