algorithm

Lucky Numbers

Lucky Number

In number theory, a lucky number is a natural number in a set which is generated by a certain “sieve”. This sieve is similar to the Sieve of Eratosthenes that generates the primes, but it eliminates numbers based on their position in the remaining set, instead of their value (or position in the initial set of natural numbers).

Lucky numbers are subset of integers. Rather than going into much theory, let us see the process of arriving at lucky numbers,

Take the set of integers

1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,……

First, delete every second number, we get following reduced set.

1,3,5,7,9,11,13,15,17,19,…………

Now, delete every third number, we get

1, 3, 7, 9, 13, 15, 19,….….

Continue this process indefinitely……

Any number that does NOT get deleted due to above process is called “lucky”.

Therefore, set of lucky numbers is 1, 3, 7, 13,………

Implementations

Language Source Run it online
   
lucky_number.cpp repl.it