Assume I have following algorithm:
Two lists of numbers, first starting at 2, second starting empty.
We now follow rule:
- Add a number to first list which makes difference with latest number the smallest prime not already in either list. Add this difference to list nr 2.
After some iterations we will get:
[2,5,12,23,36,53,...] with primes 5,23,53
[3,7,11,13,17,...] with (by construction) all members a prime, but lacking precisely the ones in list 1.
Example of executing algorithm:
- First state 2 is only prime in either list, smallest prime is 3, so we add it as new element: Now we have [2,2+3] first list, [3] second list
- Next state is [2,5], [3], we see smallest prime not in either list is 7, so we update [2,5,5+7],[3,7]
- Next state is [2,5,12], [3,7], smallest prime not in either is 11, so we update: [2,5,12,12+11], [3,7,11]
- Next state is [2,5,12,23], [3,7,11], smallest prime not in either is 13, so we update : [2,5,12,23+13], [3,7,11,13]
- And so on
We will get one subset of primes in list 2 and it's complement will be another subset of primes.
Can we say anything about how large percent of primes will be in first list after say, $n$ iterations?
Almost all primes will end up in the second list.
Because the differences between successive elements of the first list start at $3$ and increase by at least $2$ each time, it is easy to show by induction that the $n$th term of the first list is at least $n^2$. Thus of the first $N$ integers, at most $\sqrt N$ appear in the first list.
However, by the prime number theorem, of the first $N$ integers about $\frac{N}{\log N}$ are prime. At most $\sqrt N$ of these primes are in the first list, so the proportion of primes less than $N$ which appear in the first list is about $\frac{\log N}{\sqrt{N}}$, and tends to $0$.