cp's OEIS Frontend

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

%I A141436 #42 Feb 05 2018 17:02:12
%S A141436 1,3,5,8,10,11,14,15,16,17,20,22,24,25,27,30,31,32,33,35,36,38,39,40,
%T A141436 41,44,46,48,49,50,51,54,55,56,58,59,62,63,64,66,67,68,69,70,72,75,76,
%U A141436 77,78,80,82,83,85,86,87,88,90,92,93,94,96,99,100,102,104,105,108,109,110,111
%N A141436 Tisdale's sieve: generators for an infinite set of disjoint prime/nonprime sequences (see Comments for precise definition).
%C A141436 The definition: (Start)
%C A141436 Let P = (2,3,5,...) and N = (1,4,6,...) denote the sequences of primes and nonprimes, respectively.
%C A141436 Construct an infinite collection of disjoint sequences S_1, S_2, S_3, ... as follows.
%C A141436 For S_i, the first term S_i(1) is the smallest positive integer not yet used in any S_j with j < i.
%C A141436 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.
%C A141436 Then the sequence consists of the initial values S_1(1), S_2(1), S_3(1), ...
%C A141436 We find that S_1 = {1,2,4,7,12,...} (A280028), with smallest missing number 3,
%C A141436 S_2 = {3,6,13,...} (A280029), so now the smallest missing number is 5,
%C A141436 S_3 = {5,9,23,...} (A280030), and so on.
%C A141436 So the sequence begins 1,3,5,...
%C A141436 (End)
%C A141436 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
%C A141436 The complementary sequence is 2, 4, 6, 7, 9, 12, 13, 18, 19, etc., see A141437.
%C A141436 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.}."
%H A141436 B. D. Swan, <a href="/A141436/b141436.txt">Table of n, a(n) for n = 1..100000</a>
%F A141436 Conjecture: Equals A102615 UNION A006450. - _R. J. Mathar_, Aug 14 2008
%F A141436 Proof of Conjecture, from _David Applegate_, Dec 28 2016: (Start)
%F A141436 First, a simple lemma about simple sieves (doesn't apply to the Sieve of Eratosthenes):
%F A141436 Lemma: Let f be a function mapping positive integers to positive integers, with f(n) > n for all n.
%F A141436 Construct an infinite collection of (not necessarily disjoint) sequences S_1, S_2, S_3, ... as follows.
%F A141436 For S_i, the first term S_i(1) is the smallest positive integer not yet used in any S_j with j < i.
%F A141436 Thereafter S_i is extended by the rule S_i(j+1) = f(S_i(j)) = f^j (S_i(1)).
%F A141436 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().
%F A141436 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.
%F A141436 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).
%F A141436 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:
%F A141436 primes p such that p does not equal P(n) for n nonprime (A006450) and
%F A141436 nonprimes n such that n does not equal N(p) for p prime (A192615).
%F A141436 (End)
%Y A141436 Cf. A018252, A141437, A102615, A006450, A280028, A280029, A280030.
%K A141436 easy,nonn
%O A141436 1,2
%A A141436 _Daniel Tisdale_, Aug 06 2008
%E A141436 Edited (including a new name) by _N. J. A. Sloane_, Dec 25 2016