Skip to main content

Polite number

A polite number is a positive integer that can be expressed as the sum of two or more consecutive positive integers. For example, the number 6 is a polite number because it can be expressed as the sum of three consecutive positive integers: 1 + 2 + 3 = 6.

Problem Statement

The task is to write a program that prints the first 'k' polite numbers, where 'k' is a given positive integer.

For example, if 'k' is 10, the program should print the following polite numbers:

1, 3, 5, 6, 7, 9, 10, 11, 12, 13

Explanation with an Example

Let's take the example of finding the first 10 polite numbers.

To find the polite numbers, we can use the following formula:

n + (log(n + log(n)) / log(2))

Starting from 'n = 1', we iterate up to 'k' and calculate the nth polite number using the formula. We then display the calculated result.

For 'n = 1', the calculation is as follows:

n + (log(n + log(n)) / log(2)) = 1 + (log(1 + log(1)) / log(2)) = 1

Similarly, for 'n = 2', the calculation is:

n + (log(n + log(n)) / log(2)) = 2 + (log(2 + log(2)) / log(2)) = 3

By following this process for 'k' iterations, we obtain the polite numbers.

Algorithm

  1. Define a function politeNo(k) that takes the number of polite numbers to be generated as input.
  2. Initialize a loop variable 'n' from 1 to 'k'.
  3. Inside the loop, calculate the nth polite number using the formula: n + (log(n + log(n)) / log(2)).
  4. Display the calculated polite number.
  5. Repeat steps 2-4 until the desired number of polite numbers are generated.
  6. In the main function, call politeNo(k), where 'k' is the number of polite numbers to be generated.

Pseudocode

politeNo(k)
  for n = 1 to k
    result = n + (log(n + (log(n) / log(2)))) / log(2)
    print result

main()
  politeNo(k)

Code Solution

Here given code implementation process.

// C Program for
// Polite number
#include <stdio.h>
#include <math.h>

void politeNo(int k)
{
	// Print all initial k Polite number
	for (int n = 1; n <= k; ++n)
	{
		// Formula
		//    n + (log (n+log n) 
		//            ²      ²
		// Calculate nth Polite number
		int result = (int)(n + 
                           (log((n + (log(n) / log(2))))) / 
                              log(2));
		// Display calculated result
		printf("  %d", result);
	}
}
int main()
{
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56 etc.
	// k = 10
	politeNo(10);
	return 0;
}

Output

  1  3  5  6  7  9  10  11  12  13
// Java program for
// Polite number
public class PoliteNumber
{
	public void politeNo(int k)
	{
		// Print all initial k Polite number
		for (int n = 1; n <= k; ++n)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
			// Calculate nth Polite number
			int result = (int)(n + 
                               (Math.log((n + (Math.log(n) / 
                                               Math.log(2))))) /
                               Math.log(2));
			// Display calculated result
			System.out.print(" " + result);
		}
	}
	public static void main(String[] args)
	{
		PoliteNumber task = new PoliteNumber();
		//  Polite number are
		// —————————————————————————————————————————————
		//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
		//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
		//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
		//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
		//  53, 54, 55, 56 etc.
		// k = 10
		task.politeNo(10);
	}
}

Output

 1 3 5 6 7 9 10 11 12 13
// Include header file
#include <iostream>
#include <math.h>

using namespace std;
// C++ program for
// Polite number
class PoliteNumber
{
	public: void politeNo(int k)
	{
		// Print all initial k Polite number
		for (int n = 1; n <= k; ++n)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
			// Calculate nth Polite number
			int result = (int)(n + 
                               (log((n + (log(n) / 
                                          log(2))))) / 
                               log(2));
			// Display calculated result
			cout << " " << result;
		}
	}
};
int main()
{
	PoliteNumber *task = new PoliteNumber();
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
	// k = 10
	task->politeNo(10);
	return 0;
}

Output

 1 3 5 6 7 9 10 11 12 13
// Include namespace system
using System;
// Csharp program for
// Polite number
public class PoliteNumber
{
	public void politeNo(int k)
	{
		// Print all initial k Polite number
		for (int n = 1; n <= k; ++n)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
          
			// Calculate nth Polite number
			int result = (int)(n + 
                               (Math.Log((n + 
                                          (Math.Log(n) /
                                           Math.Log(2))))) / 
                               Math.Log(2));
			// Display calculated result
			Console.Write(" " + result);
		}
	}
	public static void Main(String[] args)
	{
		PoliteNumber task = new PoliteNumber();
		//  Polite number are
		// —————————————————————————————————————————————
		//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
		//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
		//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
		//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
		//  53, 54, 55, 56 etc.
      
		// k = 10
		task.politeNo(10);
	}
}

Output

 1 3 5 6 7 9 10 11 12 13
package main
import "math"
import "fmt"
// Go program for
// Polite number

func politeNo(k int) {
	// Print all initial k Polite number
	for n := 1 ; n <= k ; n++ {
		// Formula
		//    n + (log (n+log n) 
		//            ²      ²

		// Calculate nth Polite number
		var result int = (int)(float64(n) + 
			(math.Log((float64(n) + 
				(math.Log(float64(n)) / 
					math.Log(2.0))))) /
					 math.Log(2.0))
		
		// Display calculated result
		fmt.Print(" ", result)
	}
}
func main() {

	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
  
	// k = 10
	politeNo(10)
}

Output

 1 3 5 6 7 9 10 11 12 13
<?php
// Php program for
// Polite number
class PoliteNumber
{
	public	function politeNo($k)
	{
		// Print all initial k Polite number
		for ($n = 1; $n <= $k; ++$n)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
          
			// Calculate nth Polite number
			$result = (int)($n + 
                            (log(($n + (log($n) / log(2))))) / 
                            log(2));
			// Display calculated result
			echo(" ".$result);
		}
	}
}

function main()
{
	$task = new PoliteNumber();
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
	// k = 10
	$task->politeNo(10);
}
main();

Output

 1 3 5 6 7 9 10 11 12 13
// Node JS program for
// Polite number
class PoliteNumber
{
	politeNo(k)
	{
		// Print all initial k Polite number
		for (var n = 1; n <= k; ++n)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
			// Calculate nth Polite number
			var result = parseInt(n + 
                               (Math.log((n + (Math.log(n) / 
                                               Math.log(2))))) / 
                               Math.log(2));
			// Display calculated result
			process.stdout.write(" " + result);
		}
	}
}

function main()
{
	var task = new PoliteNumber();
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
	// k = 10
	task.politeNo(10);
}
main();

Output

 1 3 5 6 7 9 10 11 12 13
import math
#  Python 3 program for
#  Polite number
class PoliteNumber :
	def politeNo(self, k) :
		n = 1
		#  Print all initial k Polite number
		while (n <= k) :
			#  Formula
			#     n + (log (n+log n) 
			#             ²      ²
            
			#  Calculate nth Polite number
			result = (int)(n + 
                           (math.log((n + 
                                      (math.log(n) / 
                                       math.log(2))))) / 
                           math.log(2))

			#  Display calculated result
			print(" ", result, end = "")
			n += 1
		
	

def main() :
	task = PoliteNumber()
	#   Polite number are
	#  —————————————————————————————————————————————
	#   1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	#   18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	#   30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	#   43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	#   53, 54, 55, 56 etc.
    
	#  k = 10
	task.politeNo(10)

if __name__ == "__main__": main()

Output

  1  3  5  6  7  9  10  11  12  13
#  Ruby program for
#  Polite number
class PoliteNumber 
	def politeNo(k) 
		n = 1
		#  Print all initial k Polite number
		while (n <= k) 
			#  Formula
			#     n + (log (n+log n) 
			#             ²      ²
            
			#  Calculate nth Polite number
			result = (n + 
                           (Math.log((n + 
                                      (Math.log(n) /
                                       Math.log(2))))) / 
                           Math.log(2)).to_i
			#  Display calculated result
			print(" ", result)
			n += 1
		end

	end

end

def main() 
	task = PoliteNumber.new()
	#   Polite number are
	#  —————————————————————————————————————————————
	#   1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	#   18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	#   30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	#   43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	#   53, 54, 55, 56 etc.
	#  k = 10
	task.politeNo(10)
end

main()

Output

 1 3 5 6 7 9 10 11 12 13
// Scala program for
// Polite number
class PoliteNumber()
{
	def politeNo(k: Int): Unit = {
		var n: Int = 1;
		// Print all initial k Polite number
		while (n <= k)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
          
			// Calculate nth Polite number
			var result: Int = (n + 
                               (Math.log((n + 
                                          (Math.log(n) / 
                                           Math.log(2))))) / 
                               Math.log(2)).toInt;
          
			// Display calculated result
			print(" " + result);
			n += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: PoliteNumber = new PoliteNumber();
		//  Polite number are
		// —————————————————————————————————————————————
		//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
		//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
		//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
		//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
		//  53, 54, 55, 56 etc.
  
		// k = 10
		task.politeNo(10);
	}
}

Output

 1 3 5 6 7 9 10 11 12 13
import Foundation;
// Swift 4 program for
// Polite number
class PoliteNumber
{
	func politeNo(_ k: Int)
	{
		var n: Int = 1;
		// Print all initial k Polite number
		while (n <= k)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
			// Calculate nth Polite number
			let result: Int = 
              Int((Double(n) + 
                   (log((Double(n) + 
                         (log(Double(n)) / log(2.0))))) / 
                   log(2.0)));
			// Display calculated result
			print(" ", result, terminator: "");
			n += 1;
		}
	}
}
func main()
{
	let task: PoliteNumber = PoliteNumber();
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
	// k = 10
	task.politeNo(10);
}
main();

Output

  1  3  5  6  7  9  10  11  12  13
// Kotlin program for
// Polite number
class PoliteNumber
{
	fun politeNo(k: Int): Unit
	{
		var n: Int = 1;
		// Print all initial k Polite number
		while (n <= k)
		{
			// Formula
			//    n + (log (n+log n) 
			//            ²      ²
			// Calculate nth Polite number
			val result: Int = 
              (n + (Math.log((n.toDouble() + 
                              (Math.log(n.toDouble()) / 
                               Math.log(2.0))))) / 
               Math.log(2.0)).toInt();
			// Display calculated result
			print(" " + result);
			n += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: PoliteNumber = PoliteNumber();
	//  Polite number are
	// —————————————————————————————————————————————
	//  1, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 
	//  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
	//  30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 
	//  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 
	//  53, 54, 55, 56 etc.
	// k = 10
	task.politeNo(10);
}

Output

 1 3 5 6 7 9 10 11 12 13

Time Complexity

The time complexity of the program depends on the value of 'k', which represents the number of polite numbers to be generated.

Since we iterate from 'n = 1' to 'k' and perform constant time operations inside the loop, the time complexity can be approximated as O(k).

Output

The output of the program is a list of the first 'k' polite numbers.

For example, if 'k' is 10, the output will be:

1 3 5 6 7 9 10 11 12 13

This indicates that the first 10 polite numbers are 1, 3, 5, 6, 7, 9, 10, 11, 12, and 13.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment