Un número de cortesía es un entero positivo que se puede escribir como la suma de dos o más enteros positivos consecutivos. Dado N, encuentre el N-ésimo número de cortesía.
Ejemplos:
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.
Existe un patrón interesante de que solo las potencias de 2 no están presentes en series de números Cortés. En base a este hecho, existe la siguiente fórmula ( teorema de Lambek-Moser ) para el N-ésimo número educado.
Aquí, para encontrar el enésimo número de cortesía, tenemos que tomar n como n+1 en la ecuación anterior.
La función de registro incorporada calcula log base-e, por lo que dividirlo por log base-e 2 dará el valor de log base-2.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
11
Referencia: Wikipedia