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,
- etc.
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 ?
Edit
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).
Best Answer
So, let's see if I can precisify your claim. We start with a finite "seed set" that we assert to be Ghi-Om-prime (the seed set must not contain 1). Numbers smaller than the largest seed we completely ignore. Now for numbers larger than any seed prime, we run the Seive. You claim that there is some cut-off, depending of course on the seed set but hopefully not growing too quickly, so that after that cut-off, the primes match the primes in the seed set.
Recall how the Seive works. A number is GO-prime iff it is not divisible by any smaller GO-prime. Conversely, the GO-composites are precisely those numbers that are divisible by some smaller number that is either in your seed set or larger than the largest number in the seed set. In particular, every GO-composite is a true composite. So suppose there is a true composite that is not GO-composite. Then all its proper divisors are less than the largest seed. But every non-prime has a proper divisor that is at least as large as its square root. So the largest true composite that is not GO-composite is strictly less than the square of the largest seed.
This proves your claim, with the bound you suggested in the comment to Noldorin.
In any case, some remarks. First, if we state the rules for the Sieve correctly, and in particular disallow 1 as either prime or composite, then the true primes are precisely the GO primes where the seed set is empty.
Second, although I haven't seen this particular variation of the Sieve before, as I said in the comments to the question, you should check out Sanjoy Mahajan's thesis (PDF). In the last chapter, he proposes the following probabilistic variation of the Sieve. Namely, let's define the probability that $p$ SM-divides $n$ to be $1/p$. Then the probability that $n$ is SM-prime is $$ \prod_{p < \sqrt n} (\text{probability that $p$ is SM-prime})\times (\text{probability that $p$ does not SM-divide $n$})$$ The point is that SM-primality is nicely smooth, rather than exhibiting the strange jumps in the true prime spectrum, but still approximates the spectrum well for certain types of estimates. Sanjoy also considers a few other probabilistic models (whether to stop the product at $\sqrt n$ or $n$, for example), including some where he seeds the model with some early assertions of SM-primality. Sanjoy is a physicist, and so does not work at mathematicians' level of rigor, and says as much: the point of his model is to lead to new conjectures about distribution of true primes.