2
$\begingroup$

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:

  1. 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
  2. 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]
  3. 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]
  4. 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]
  5. 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?

$\endgroup$
  • $\begingroup$ Do I understand correctly that on each step we choose the smallest prime $p$ not yet in lists, add it to the second list, then take the last element $a$ from the first list and add $a + p$ to the first list? $\endgroup$ – mihaild May 22 at 9:14
  • $\begingroup$ @mihaild I think you may be right, but I am not sure so I made explanation in steps how lists are built in example. $\endgroup$ – mathreadler May 22 at 9:20
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ This is what I would expect too! Which kind of make these odd birds extra interesting.. $\endgroup$ – mathreadler May 22 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.