3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Is it integers, or non-negative integers, or positive integers? $\endgroup$ Feb 7, 2013 at 3:22
  • $\begingroup$ Positive integers . $\endgroup$ Feb 7, 2013 at 3:30

3 Answers 3

2
$\begingroup$

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)$

$\endgroup$
3
  • $\begingroup$ Can you give an example to clarify your solution ? That will be too useful for me . $\endgroup$ Feb 7, 2013 at 3:17
  • $\begingroup$ What do you want to tell by the following statement ? 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 .... $\endgroup$ Feb 13, 2013 at 4:49
  • $\begingroup$ Can you give me more realistic example . Take a number say 15000 . What steps should I follow to find the number of ways by which 1500 can be expressed as sum of consecutive positive natural integers ? $\endgroup$ Feb 13, 2013 at 4:51
1
$\begingroup$

LET, N be the number. your ans is the number of odd divisor of N -1. u can easily calculate the number of odd divisors. eg. 1,3,5,15 r the odd divisors of N so your ans is 4-1=3

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to MSE. Why does this approach work? Does it generalise to other numbers as well? $\endgroup$
    – Daryl
    May 3, 2013 at 5:52
  • $\begingroup$ Niaz kmn achs ? Thanks for your answer . $\endgroup$ Aug 31, 2013 at 1:07
1
$\begingroup$

The meaning of the questions: given n, n can be written in the form of at least two consecutive positive integers and the number of species.

Ideas: Let n can be written as a, a +1, a +2 ...... a + k-1's and (a> = 1), i.e., n = (a + a + k-1) * k / 2. If k is odd, then, N = (A + (k-1) / 2) * k If k is even, then (a + a + k-1) is an odd number. So if there are a set of solutions, must correspond to an odd prime. The following proved, a odd prime number other than 1, each odd prime number corresponds to a solution.Let x n is an odd prime number, so that y = n / x. Then the relationship between x and y, only the following two:

(1) y> (x-1) / 2, In this case, n must be able to be written as n = (a + (k-1) / 2) * k of the form. Wherein x = K, y = a - a + (k-1) / 2, this time to meet a = y-(K-1) / 2 = y-(x-1) / 2 is a positive integer;

(2) y <= (x-1) / 2, where n must be able to be written as n = n = (a + a + k-1) * k / 2 of the form. Wherein, y = k / 2, x = a + A + k-1, this time A = (x +1- k) / 2 = (x +1- y * 2) / 2 = (x-1) / 2-y +1> = 1.

Therefore, an odd prime number must correspond to a solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .