N-th polite number

0 0 2 minutes read

A polite number is a positive integer that can be written as the sum of two or more consecutive positive integers. Given N, find the N-th polite number.
Examples:

Input : 4
Output : 7
Explanation: The first 3 are 3(1+2), 5(2+3), 
             6(1+2+3).

Input : 7
Output : 11
Explanation:  3, 5, 6, 7, 9, 10, 11.

There exist an interesting pattern that only powers of 2 are not present in series of Polite numbers. Based on this fact, there exist below formula (Lambek–Moser theorem) for N-th polite number.
$f(n) = n+ \left \lfloor log_2 (n+ log_2 n) \right \rfloor$
Here to find Nth polite number we have to take n as n+1 in the above equation
The inbuilt log function computes log base-e, so dividing it by log base-e 2 will give log base-2 value.
Given below is the implementation of the above approach:

C++

// CPP program to find Nth polite number
#include <bits/stdc++.h>
using namespace std;
 
// function to evaluate Nth polite number
double polite(double n)
{
    n += 1;
    double base = 2;
    return n + (log((n + (log(n) /
                 log(base))))) / log(base);
}
 
// driver code
int main()
{
    double n = 7;
 
    cout << (int)polite(n);
    return 0;
}

Java

// Java program for finding N-th polite number
import java.io.*;
 
class GFG {
 
    // function to find N-th polite number
    static double polite(double n)
    {
        n += 1;
        double base = 2;
        return n + (Math.log((n + (Math.log(n) / 
               Math.log(base))))) / Math.log(base);
    }
 
    // driver code
    public static void main(String[] args)
    {
        double n = 7;
        System.out.println((int)polite(n));
    }
}

Python

import math
# function to find Nth polite number 
def Polite(n):
    n = n + 1
    return (int)(n+(math.log((n + math.log(n, 2)), 2))) 
 
# Driver code
n = 7
print Polite(n)

C#

// Java program for finding 
// N-th polite number
using System;
 
class GFG {
 
    // Function to find N-th polite number
    static double polite(double n)
    {
        n += 1;
        double base1 = 2;
        return n + (Math.Log((n + (Math.Log(n) / 
                     Math.Log(base1))))) / 
                     Math.Log(base1);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        double n = 7;
        Console.Write((int)polite(n));
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

PHP

<?php
// PHP program to find
// Nth polite number
 
// function to evaluate 
// Nth polite number
function polite($n)
{
    $n += 1;
    $base = 2;
    return $n + (log(($n + (log($n) /
                 log($base))))) / log($base);
}
 
// Driver code
$n = 7;
echo((int)polite($n));
 
// This code is contributed by Ajit.
?>

Javascript

<script>
 
// Javascript program to find
// Nth polite number
 
// function to evaluate
// Nth polite number
function polite(n)
{
    n += 1;
    let base = 2;
    return n + (Math.log((n + (Math.log(n) /
                Math.log(base))))) / Math.log(base);
}
 
// Driver code
n = 7;
document.write(parseInt(polite(n)));
 
// This code is contributed by _saurabh_jaiswal.
 
</script>

Output:

Time complexity: O(1)
Auxiliary space: O(1)

Reference: Wikipedia

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!