OFFSET
1,2
COMMENTS
The definition: (Start)
Let P = (2,3,5,...) and N = (1,4,6,...) denote the sequences of primes and nonprimes, respectively.
Construct an infinite collection of disjoint sequences S_1, S_2, S_3, ... as follows.
For S_i, the first term S_i(1) is the smallest positive integer not yet used in any S_j with j < i.
Thereafter S_i is extended by the rule S_i(j+1) = either P(S_i(j)) or N(S_i(j)), where we choose P or N so that the primes and nonprimes alternate in S_i.
Then the sequence consists of the initial values S_1(1), S_2(1), S_3(1), ...
We find that S_1 = {1,2,4,7,12,...} (A280028), with smallest missing number 3,
S_2 = {3,6,13,...} (A280029), so now the smallest missing number is 5,
S_3 = {5,9,23,...} (A280030), and so on.
So the sequence begins 1,3,5,...
(End)
Note that the disjointness is a consequence of the definition. For if S_i and S_j have a common term, let S_i(q) = S_j(r) = X (say) be the first time they meet. Then either one or both of q and r are 1, which is impossible by the construction, or q > 1, r > 1. But then S_i(q-1) = S_j(r-1), which is a contradiction. - N. J. A. Sloane, Dec 28 2016
The complementary sequence is 2, 4, 6, 7, 9, 12, 13, 18, 19, etc., see A141437.
The old definition was: "a(k) = k-th prime or nonprime: a(k+1) = a(a(k)); if k is prime, a(k) is nonprime; if k is nonprime, a(k) is prime. {a(1)} = {1,2,4,7,12,...}, {a(3)} = {3,6,13,...}, {a(5)} = {5,9,23,...}. The generators of these mutually disjoint sets are the first elements, {1,3,5,8, etc.}."
LINKS
B. D. Swan, Table of n, a(n) for n = 1..100000
FORMULA
Proof of Conjecture, from David Applegate, Dec 28 2016: (Start)
First, a simple lemma about simple sieves (doesn't apply to the Sieve of Eratosthenes):
Lemma: Let f be a function mapping positive integers to positive integers, with f(n) > n for all n.
Construct an infinite collection of (not necessarily disjoint) sequences S_1, S_2, S_3, ... as follows.
For S_i, the first term S_i(1) is the smallest positive integer not yet used in any S_j with j < i.
Thereafter S_i is extended by the rule S_i(j+1) = f(S_i(j)) = f^j (S_i(1)).
Then the sequence of initial values S_1(1), S_2(1), S_3(1), ... consists of the positive integers not in the image of f().
Proof: Obviously, if n is not in the image of f(), it can never occur as S_i(j) for j > 1, so it will eventually occur as S_i(1) for some i.
Conversely, if n is in the image of f(), it will occur as S_i(j) for some i and j > 1 such that S_i(1) < n, and hence will not occur as an initial value. We show this by induction n: Let n = f(m) (so m < n). If m is in the image of f(), then by induction it occurs as S_i(j) for some i and j>1, so n=S_i(j+1). Otherwise, if m is not in the image of f(), then it will occur as S_i(1) for some i, so n=S_i(2).
To apply the lemma, just define f(n) = P(n) if n is nonprime, N(n) if n is prime. So, the sequence of initial values will consist of:
primes p such that p does not equal P(n) for n nonprime (A006450) and
nonprimes n such that n does not equal N(p) for p prime (A192615).
(End)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Daniel Tisdale, Aug 06 2008
EXTENSIONS
Edited (including a new name) by N. J. A. Sloane, Dec 25 2016
STATUS
approved