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
- Define a function politeNo(k) that takes the number of polite numbers to be generated as input.
- Initialize a loop variable 'n' from 1 to 'k'.
- Inside the loop, calculate the nth polite number using the formula: n + (log(n + log(n)) / log(2)).
- Display the calculated polite number.
- Repeat steps 2-4 until the desired number of polite numbers are generated.
- 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 13package 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 13import 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 13import 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 13Time 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.
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