S reads like this:
"At position 2, there is a prime in S" [indeed, this is 3]
"At position 3, there is a prime in S" [indeed, this is 5]
"At position 5, there is a prime in S" [indeed, this is 7]
"At position 1, there is a prime in S" [indeed, this is 2]
"At position 7, there is a prime in S" [indeed, this is 11]
"At position 8, there is a prime in S" [indeed, this is 13]
"At position 11, there is a prime in S" [indeed, this is 19]
"At position 13, there is a prime in S" [indeed, this is 23]
"At position 10, there is a prime in S" [indeed, this is 17], etc.
S is built with this rule: when you are about to write a term of S, always use the smallest integer not yet present in S and not leading to a contradiction.
Thus one cannot start with 1; this would read: "At position 1, there is a prime number in S" [no, 1 is not a prime]
So start S with 2 and the rest follows smoothly.
S contains all the primes and they appear in their natural order.
Does the ratio primes/composites in S tend to a limit? Answer (from Dean Hickerson): Yes, to 1/2.
Comments from Dean Hickerson, Aug 11 2006: (Start)
In the limit, exactly half of the terms are primes. Here's a formula, found empirically, for a(n) for n >= 5:
Let pi(n) be the number of primes <= n and p(n) be the nth prime. Then:
 if n is prime or (n is composite and n+pi(n) is even) then a(n) = p(floor((n+pi(n))/2));
 if n is composite and n+pi(n) is odd and n+1 is composite then a(n) = n+1;
 if n is composite and n+pi(n) is odd and n+1 is prime then a(n) = n+2.
Also, for n >= 5, n is in the sequence iff either n is prime or n+pi(n) is even.
(This could all be proved by induction on n.)
It follows from this that, for n >= 4, the number of primes among a(1), ..., a(n) is exactly floor((n+pi(n))/2. Since pi(n)/n > 0 as n > infinity, this is asymptotic to n/2. (End)
