Tuesday, May 6, 2014

Polite Numbers - Calculate all the ways such that a number can be written as sum of 2 or more consecutive numbers

Problem

Write a program that calculates all the ways that a number can be written as the sum of two or more consecutive numbers and generate those sets.

Background

 In number theory, a polite number is a positive integer that can be written as the sum of two or more consecutive positive integers.

The first few polite numbers are
3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17,...

For instance, 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8. The number of ways that a number can be written as the sum of two or more consecutive numbers is its politeness. Any number that is a power of 2 cannot be written as the sum of two or more consecutive numbers; such a number has a politeness of 0, and is thus impolite.

Here is the code:
int countNumberOfPoliteWays(int n)
{
 int n,sum,i,j,k,q=0,count=0;

 for( i=n/2+1; i > 1; i-- )
 {
  sum=i;
  for( j=i-1; j > 0; j-- )
  {
   sum=sum+j;
   if( sum==n )
   {
    count++;
    if( j==1 ) 
     q=1;

    for( k=j; k <= i; k++ ) 
     out.print(k);

    out.println();
    break;
   }
   else if( sum > n ) 
     break;
  }
  if( q ) 
   break;
 }

 return count;
}

References

0 comments:

Post a Comment