A141436 Tisdale's sieve: generators for an infinite set of disjoint prime/nonprime sequences (see Comments for precise definition).

1, 3, 5, 8, 10, 11, 14, 15, 16, 17, 20, 22, 24, 25, 27, 30, 31, 32, 33, 35, 36, 38, 39, 40, 41, 44, 46, 48, 49, 50, 51, 54, 55, 56, 58, 59, 62, 63, 64, 66, 67, 68, 69, 70, 72, 75, 76, 77, 78, 80, 82, 83, 85, 86, 87, 88, 90, 92, 93, 94, 96, 99, 100, 102, 104, 105, 108, 109, 110, 111

Offset: 1

Author

Daniel Tisdale, Aug 06 2008

Keywords

• easy
• nonn

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

Crossrefs

Cf. A018252, A141437, A102615, A006450, A280028, A280029, A280030.

Formula

Conjecture: Equals A102615 UNION A006450. - R. J. Mathar, Aug 14 2008

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)

Extensions

Edited (including a new name) by N. J. A. Sloane, Dec 25 2016