It occured to me that the Sieve of Eratosthenes eventually generates the same prime numbers, independently of the ones chosen at the beginning. (We generally start with 2, but we could chose any finite set of integers >= 2, and it would still end up generating the same primes, after a "recalibrating" phase).
If I take 3 and 4 as my first primes, starting at 5:
- 5 is prime,
- 6 is not (twice 3),
- 7 is prime,
- 8 is not,
- 9 is not,
- 10 is not,
Eventually, I will find all the primes as if I had started with 2 only.
To me, it means that we can generate big prime numbers without any knowledge of their predecessors (until a certain point). If I want primes higher than 1000000, then I can generate them without any knowledge of primes under, say, 1000. (It may not be as effective computationnally, but I find this philosophically interesting.)
Is this result already known ?
Are there any known implications ?
The number from which we are assured to get the right primes again is after the square of the last missing natural prime.
That is, if I start with a seed set containing only the number 12, the highest missing natural prime is 11, so I'll end up having 121 as my last not-natural prime. Non-natural primes found are 12,14,15,16,18,20,21,22,25,27,33,35,49,55,77 and 121.
This is a bit better than what I thought at first (namely, as stated below, somewhere under the square of the highest seed).