Innumber theory, alucky number is anatural number in a set which is generated by a certain "sieve". This sieve is similar to thesieve of Eratosthenes that generates theprimes, 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).[1]
The term was introduced in 1956 in a paper by Gardiner, Lazarus,Metropolis andUlam. In the same work they also suggested calling another sieve, "the sieve ofJosephus Flavius"[2] because of its similarity with the counting-out game in theJosephus problem.
Lucky numbers share some properties with primes, such as asymptotic behaviour according to theprime number theorem; also, a version ofGoldbach's conjecture has been extended to them. There are infinitely many lucky numbers. Twin lucky numbers andtwin primes also appear to occur with similar frequency. However, ifLn denotes then-th lucky number, andpn then-th prime, thenLn >pn for all sufficiently largen.[3]
Because of their apparent similarities with the prime numbers, some mathematicians have suggested that some of their common properties may also be found in other sets of numbers generated by sieves of a certain unknown form, but there is little theoretical basis for thisconjecture.
An animation demonstrating the lucky number sieve. The numbers on a reddish orange background are lucky numbers. When a number is eliminated its background changes from grey to purple. Chart goes to 120.
Every second number (alleven numbers) in the list is eliminated, leaving only the odd integers:
1
3
5
7
9
11
13
15
17
19
21
23
25
The first number remaining in the list after 1 is 3, so every third number (beginning at 1) which remains in the list (not every multiple of 3) is eliminated. The first of these is 5:
1
3
7
9
13
15
19
21
25
The next surviving number is now 7, so every seventh remaining number is eliminated. The first of these is 19:
1
3
7
9
13
15
21
25
Continue removing thenth remaining numbers, wheren is the next number in the list after the last surviving number. Next in this example is 9.
One way that the application of the procedure differs from that of the Sieve of Eratosthenes is that forn being the number being multiplied on a specific pass, the first number eliminated on the pass is then-th remaining number that has not yet been eliminated, as opposed to the number2n. That is to say, the list of numbers this sieve counts through is different on each pass (for example 1, 3, 7, 9, 13, 15, 19... on the third pass), whereas in the Sieve of Eratosthenes, the sieve always counts through the entire original list (1, 2, 3...).
When this procedure has been carried out completely, the remaining integers are the lucky numbers (those that happen to be prime are in bold):
