The lucky numbers are a set of positive
integers discovered by
Stanislaw Ulam. They are generated by a method similar to the
sieve of Erastosthenes (used to generate the
primes). To construct the luckies, begin with the set of
natural numbers, and remove every
nth number, where
n is the first integer greater than 1 which appears in the set and has not yet been used as a sieve. Repeating
ad infinitum leaves behind the
infinite set of lucky numbers. To clarify, a few iterations of the sieve are shown below.
Start with the natural numbers:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Now 2 is the first number greater than 1, so remove every second element:
1 3 5 7 9 11 13 15 17 19 ...
The smallest integer greater than 1 which remains is 3, so remove every third element:
1 3 7 9 13 15 19 ...
Now 3 is still the smallest remaining number greater than 1, however it's already been used at the previous step so we move on to 7 and remove every seventh number:
1 3 7 9 13 15 ...
...and so on (next, we would remove every ninth element remaining in the set). The first ten lucky numbers are 1, 3, 7, 9, 13, 15, 21, 25, 31, and 33.
Interestingly, the lucky numbers share many properties with the primes, suggesting that these properties arise from the sieving process rather than the fact that primes have no factors. Lucky numbers are distributed throughout the integers with roughly the same density as the primes, and other similarities appear between the distribution of twin primes and twin luckies (pairs of lucky numbers which differ by 2). It is even conjectured that every even number is the sum of two luckies, an analogue of Goldbach's conjecture.