Represent a number as sum of consecutive numbers

Правка en6, от rootn, 2017-08-12 21:16:29

In how many ways can you represent a number as the sum of consecutive numbers.

To solve this, we can use the concept of A.P. We know that sum of A.P. is n = (m/2)*(2*a + (m - 1)*d) if n is the sum and m is the number of integers with common difference d in the A.P. In our problem, n is the given number and m is the number of consecutive integers, obviously d is 1. Now we can derive two conclusions from above formula:

  1. Manipulating the above formula as n/m = m/2 + (a - 1/2) we can see that n/m is definitely greater than m/2 because (a - 1/2) is always positive as 'a' belongs to the range [1, INF). Therefore, the conclusion is n/m > m/2 => m < sqrt(2n).

  2. Above formula can also be written as a = n/m - m/2 + 1/2.From here we can conclude that n/m - m/2 + 1/2 is an integer as a is integer.

So if we iterate over m from 2 to sqrt(2n) and check for every such m that n/m - m/2 + 1/2 is integer or not. If we count the number of m's for which n/m - m/2 + 1/2 is integer then that count will be the number of ways in which we can represent n as sum of consecutive numbers.

int count = 0;
for(int i = 2;i < sqrt(2n);i++)
{
    //If n/m - m/2 + 1/2 is integer: count++
}
count is the no. of ways.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский rootn 2021-02-13 06:22:51 2 Tiny change: 'r(int i = 2;i < sqrt(' -> 'r(int i = 1;i < sqrt('
en7 Английский rootn 2017-08-12 21:19:00 20 Tiny change: 'at n/m is definitely greater t' -> 'at n/m is greater t'
en6 Английский rootn 2017-08-12 21:16:29 16
en5 Английский rootn 2017-08-12 21:15:30 22
en4 Английский rootn 2017-08-11 12:55:51 36
en3 Английский rootn 2017-08-11 12:41:51 2 Tiny change: 'r(int i = 0;i < sqrt(' -> 'r(int i = 2;i < sqrt('
en2 Английский rootn 2017-08-09 20:43:23 182
en1 Английский rootn 2017-08-09 15:29:17 1181 Initial revision (published)