Números de la suerte

Los números de la suerte son un subconjunto de los números enteros. En lugar de entrar en mucha teoría, veamos el proceso de llegar a los números de la suerte. 
Tome el conjunto de números enteros 
1,2,3,4,5,6,7,8,9,10,11,12,13,14 ,15,16,17,18,19,……
Primero, elimine cada segundo número, obtenemos el siguiente conjunto reducido. 
1,3,5,7,9,11,13,15,17,19,…………
Ahora, borra cada tercer número, obtenemos 
1, 3, 7, 9, 13, 15, 19,….… .
Continúe este proceso indefinidamente… 
Cualquier número que NO se elimine debido al proceso anterior se llama «suerte».
Por lo tanto, el conjunto de números de la suerte es 1, 3, 7, 13,………
Ahora, dado un número entero ‘n’, escriba una función para decir si este número es afortunado o no. 

    bool isLucky(int n)

Algoritmo: 
antes de cada iteración, si calculamos la posición del número dado, entonces, en una iteración determinada, podemos determinar si el número se eliminará. Suponga que la posición calculada para el número dado es P antes de alguna iteración, y cada I-ésimo número se eliminará en esta iteración, i

f P < I entonces el número de entrada es afortunado, 

si P es tal que P%I == 0 (I es un divisor de P), entonces la entrada no no es afortunada. 

Cómo calcular la siguiente posición del número:

Sabemos que inicialmente la posición del número es el n-ésimo. Ahora cualquier posición siguiente será igual a la posición anterior menos la cantidad de elementos (o digamos elementos) eliminados.

Es decir,   next_position = current_position – recuento de números eliminados

Por ejemplo, tome el caso de n=13 .

Tenemos: Posición inicial: n, es decir. 13 en sí.  

1,2,3,4,5,6,7,8,9,10,11,12,13

Ahora, después de eliminar cada segundo elemento, en realidad eliminamos n/2 elementos. Así que ahora la posición de 13 será: nn/2=13-6=7 (n=13), i=2

1,3,5,7,9,11,13.

Después de eso, eliminamos n/3 elementos. Tenga en cuenta que n ahora es n=7. Entonces posición de 13: nn/3 = 7-7/3 = 7-2 = 5 (n=7), i=3

1,3,7,9,13

A continuación será: nn/4 = 5-5/4 = 4 (n=5), i=4

1,3,7,13

Así que ahora i=5, pero dado que la posición de 13 es solo 4, se guardará. Por lo tanto, un número de la suerte!  n=4, i=5

Manera recursiva:  

// C++ program for Lucky Numbers
#include <bits/stdc++.h>
using namespace std;
#define bool int
 
/* Returns 1 if n is a lucky no.
otherwise returns 0*/
bool isLucky(int n)
{
    static int counter = 2;
     
    if(counter > n)
        return 1;
    if(n % counter == 0)
        return 0;
     
    /*calculate next position of input no.
      Variable "next_position" is just for
    readability of the program we can
    remove it and update in "n" only */
    int next_position = n - (n/counter);
     
    counter++;
    return isLucky(next_position);
}
 
// Driver Code
int main()
{
    int x = 5;
    if( isLucky(x) )
        cout << x << " is a lucky no.";
    else
        cout << x << " is not a lucky no.";
}
 
// This code is contributed
// by rathbhupendra

#include <stdio.h>
#define bool int
 
/* Returns 1 if n is a lucky no. otherwise returns 0*/
bool isLucky(int n)
{
    static int counter = 2;
     
    if(counter > n)
        return 1;
    if(n%counter == 0)
        return 0;    
     
    /*calculate next position of input no.
      Variable "next_position" is just for
    readability of the program we can
    remove it and update in "n" only */
    int next_position = n - (n/counter);
     
    counter++;
    return isLucky(next_position);
}
 
/*Driver function to test above function*/
int main()
{
    int x = 5;
    if( isLucky(x) )
        printf("%d is a lucky no.", x);
    else
        printf("%d is not a lucky no.", x);
    getchar();
}

// Java program to check Lucky Number
import java.io.*;
 
class GFG
{
    public static int counter = 2;   
 
    // Returns 1 if n is a lucky no.
    // otherwise returns 0
    static boolean isLucky(int n)
    {
        if(counter > n)
            return true;
        if(n%counter == 0)
            return false;     
  
        /*calculate next position of input no.
        Variable "next_position" is just for
        readability of the program we can
        remove it and update in "n" only */
        int next_position = n - (n/counter);
    
        counter++;
        return isLucky(next_position);
    }
     
    // driver program
    public static void main (String[] args)
    {
        int x = 5;
        if( isLucky(x) )
            System.out.println(x+" is a lucky no.");
        else
            System.out.println(x+" is not a lucky no.");
    }
}
 
// Contributed by Pramod Kumar

# Python program to check for lucky number
 
# Returns 1 if n is a lucky number
# otherwise returns 0
def isLucky(n):
     
    # Function attribute will act
    # as static variable  
     
    if isLucky.counter > n:
        return 1
    if n % isLucky.counter == 0:
        return 0
     
    #calculate next position of input no.
      #Variable "next_position" is just for
    #readability of the program we can
    #remove it and update in "n" only
    next_position = n - (n/isLucky.counter)
     
    isLucky.counter = isLucky.counter + 1
     
    return isLucky(next_position)
     
     
# Driver Code
 
isLucky.counter = 2 # Acts as static variable
x = 5
if isLucky(x):
    print x,"is a Lucky number"
else:
    print x,"is not a Lucky number"
     
# Contributed by Harshit Agrawal

// C# program to check Lucky Number
using System;
 
class GFG {
     
    public static int counter = 2;
 
    // Returns 1 if n is a lucky no.
    // otherwise returns 0
    static bool isLucky(int n)
    {       
        if(counter > n)
            return true;
        if(n % counter == 0)
            return false;    
 
       /*calculate next position of input no.
        Variable "next_position" is just for
        readability of the program we can
        remove it and update in "n" only */
        int next_position = n - (n/counter);
     
        counter++;
         
        return isLucky(next_position);
    }
     
    // driver program
    public static void Main ()
    {
        int x = 5;
         
        if( isLucky(x) )
            Console.Write(x + " is a "
                         + "lucky no.");
        else
            Console.Write(x + " is not"
                      + " a lucky no.");
    }
}
 
// This code is contributed by
// nitin mittal.

<?php
// PHP program for Lucky Numbers
 
/* Returns 1 if n is a lucky
   no. otherwise returns 0 */
function isLucky($n)
{
    $counter = 2;
     
    if($counter > $n)
        return 1;
    if($n % $counter == 0)
        return 0;
     
    /*calculate next position of input no.
      Variable "next_position" is just for
    readability of the program we can
    remove it and update in "n" only */
    $next_position = $n - ($n / $counter);
     
    $counter++;
    return isLucky($next_position);
}
 
    // Driver Code
    $x = 5;
    if(isLucky($x) )
        echo $x ," is a lucky no.";
    else
        echo $x ," is not a lucky no.";
         
// This code is contributed by anuj_67.
?>

<script>
 
// C++ program for Lucky Numbers
 
/* Returns 1 if n is a lucky no.
otherwise returns 0*/
function isLucky(n)
{
    let counter = 2;
     
    if(counter > n)
        return 1;
    if(n % counter == 0)
        return 0;
     
   /*calculate next position of input no.
      Variable "next_position" is just for
    readability of the program we can
    remove it and update in "n" only */
    let next_position = n - Math.floor(n/counter);
     
    counter++;
    return isLucky(next_position);
}
 
// Driver Code
  
    let x = 5;
    if( isLucky(x) )
        document.write(x + " is a lucky no.");
    else
        document.write(x + " is not a lucky no.");
  
 
// This code is contributed by Mayank Tyagi
 
</script>

5 is not a lucky no.

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Ejemplo: 
Tomemos un ejemplo de 19
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15,17,18,19,20,21 ,…… 
1,3,5,7,9,11,13,15,17,19,….. 
1,3,7,9,13,15,19,………. 
1,3,7,13,15,19,……… 
1,3,7,13,19,………
En el siguiente paso, se eliminará cada sexto número .en secuencia. 19 no se eliminará después de este paso porque la posición de 19 es la quinta después de este paso. Por lo tanto, 19 es suerte. Veamos cómo se entera el código C anterior: 

Cuando se llama a isLucky(6), devuelve 1 (porque contador > n).
Escriba comentarios si encuentra algún error en los programas dados u otras formas de resolver el mismo problema.