|
| |
|
|
A141436
|
|
Tisdale's sieve: generators for an infinite set of disjoint prime/nonprime sequences (see Comments for precise definition).
|
|
8
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
FORMULA
|
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
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
