Solution of Light Online Judge -1278 - Sum of Consecutive Integers

Problem Statement :
       Given an integer N, you have to find the number of ways you can express N as sum of consecutive integers. You have to use at least two integers.For example, N = 15 has three solutions, (1+2+3+4+5), (4+5+6), (7+8).

Problem Solution Idea :

     Let 

N=2α23α35α5…qαq, where q is the largest prime dividing N.

We want N=a+(a+1)+(a+2)+(a+3)+⋯b=(b−a+1)(a+b)2, where a,b∈N

So we need to find a and b such that (b−a+1)(a+b)=2(α2+1)3α35α5…qα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∈N.

Assume that (a+b) is even. So (b−a+1) is odd.

Hence

(a+b)=2(α2+1)3β35β5…qβq

(b−a+1)=3α3−β35α5−β5…qαq−βq

where 0≤βp≤αp and (a+b)>(b−a+1)

Now assume that (a+b) is odd. So (b−a+1) is even.

Hence

(a+b)=3β35β5…qβq

(b−a+1)=2(α2+1)3α3−β35α5−β5…qαq−βq

where 0≤βp≤α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×(1+α3)×(1+α5)×(1+α7)⋯×(1+α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)

2nd Idea : 

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.