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

%I #42 Feb 05 2018 17:02:12

%S 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 41,44,46,48,49,50,51,54,55,56,58,59,62,63,64,66,67,68,69,70,72,75,76,

%U 77,78,80,82,83,85,86,87,88,90,92,93,94,96,99,100,102,104,105,108,109,110,111

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

%C The definition: (Start)

%C Let P = (2,3,5,...) and N = (1,4,6,...) denote the sequences of primes and nonprimes, respectively.

%C Construct an infinite collection of disjoint sequences S_1, S_2, S_3, ... as follows.

%C 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 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 Then the sequence consists of the initial values S_1(1), S_2(1), S_3(1), ...

%C We find that S_1 = {1,2,4,7,12,...} (A280028), with smallest missing number 3,

%C S_2 = {3,6,13,...} (A280029), so now the smallest missing number is 5,

%C S_3 = {5,9,23,...} (A280030), and so on.

%C So the sequence begins 1,3,5,...

%C (End)

%C 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 The complementary sequence is 2, 4, 6, 7, 9, 12, 13, 18, 19, etc., see A141437.

%C 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 B. D. Swan, <a href="/A141436/b141436.txt">Table of n, a(n) for n = 1..100000</a>

%F Conjecture: Equals A102615 UNION A006450. - _R. J. Mathar_, Aug 14 2008

%F Proof of Conjecture, from _David Applegate_, Dec 28 2016: (Start)

%F First, a simple lemma about simple sieves (doesn't apply to the Sieve of Eratosthenes):

%F Lemma: Let f be a function mapping positive integers to positive integers, with f(n) > n for all n.

%F Construct an infinite collection of (not necessarily disjoint) sequences S_1, S_2, S_3, ... as follows.

%F 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 Thereafter S_i is extended by the rule S_i(j+1) = f(S_i(j)) = f^j (S_i(1)).

%F 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 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 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 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 primes p such that p does not equal P(n) for n nonprime (A006450) and

%F nonprimes n such that n does not equal N(p) for p prime (A192615).

%F (End)

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

%K easy,nonn

%O 1,2

%A _Daniel Tisdale_, Aug 06 2008

%E Edited (including a new name) by _N. J. A. Sloane_, Dec 25 2016