Lucky Number — Definition, Formula & Examples
A lucky number is a natural number that survives a specific sieving process where you repeatedly remove every th remaining number, starting by eliminating every second number, then every third surviving number, and so on.
Beginning with the sequence of positive odd integers , the lucky number sieve operates iteratively: at each stage, the next value greater than 1 in the surviving list determines that every th element is removed. The numbers that are never eliminated form the sequence of lucky numbers:
How It Works
Start by listing all positive integers and remove every second one, leaving The first number greater than 1 in this list is , so remove every 3rd remaining number. The next surviving value after that hasn't been used is , so remove every 7th remaining number. You continue this pattern indefinitely, each time using the next untouched number in the list as the new sieving step. Any number that is never removed is called a lucky number.
Worked Example
Problem: Use the lucky number sieve to find all lucky numbers up to 21.
Step 1: List positive integers and remove every 2nd number (all even numbers).
Step 2: The first surviving number greater than 1 is 3. Remove every 3rd number from the current list. The 3rd, 6th, 9th, ... entries (5, 11, 17) are removed.
Step 3: The next sieving number is 7. Remove every 7th number from the current list. The 7th entry is 19.
Answer: The lucky numbers up to 21 are: 1, 3, 7, 9, 13, 15, and 21.
Why It Matters
Lucky numbers share surprising properties with prime numbers — for instance, they appear with roughly the same frequency among large integers and satisfy an analog of the Goldbach conjecture. Studying them helps build intuition about how sieve methods work, a technique central to number theory and combinatorics.
Common Mistakes
Mistake: Removing every th number from the original list instead of the current surviving list at each stage.
Correction: Each sieve step operates on the list that remains after all previous eliminations. Always count positions within the surviving sequence, not the original integers.