|
| |
|
|
A338833
|
|
Lexicographically earliest infinite sequence of distinct positive numbers with the property that a(n) is the smallest number m not yet in the sequence such that the binary expansions of m and a(n-1) have a 1 in the same position, but the positions of the 1's in the binary expansions of m and a(n-2) are disjoint.
|
|
8
|
|
|
|
1, 3, 6, 12, 9, 17, 18, 10, 13, 20, 48, 33, 5, 14, 24, 49, 7, 66, 72, 25, 19, 34, 36, 21, 11, 40, 52, 22, 67, 41, 28, 68, 65, 27, 30, 100, 97, 129, 130, 26, 29, 37, 96, 74, 15, 53, 80, 192, 131, 23, 44, 104, 81, 133, 38, 42, 73, 69, 54, 56, 136, 132, 39, 43
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This is an analog of the Enots Wolley sequence A336957 based on binary representations rather than prime factorizations.
Let Ker(k), the kernel of k, denote the set of positions of 1's in the binary expansion of k. Thus Ker(15) = {0,1,2,3}, Ker(1) = {0}.
Theorem 1: For n > 2, a(n) is the smallest number m not yet in the sequence such that:
(i) Ker(m) intersect Ker(a(n-1)) is nonempty,
(ii) Ker(m) intersect Ker(a(n-2)) is empty, and
(iii) the set Ker(m) \ Ker(a(n-1)) is nonempty.
Say that a number k is a "candidate" for a(n) if properties (i), (ii) and (iii) hold, but k is not necessarily unused nor the lowest available number with those properties.
Define the "characteristic function" of a positive integer k by char_k(i) = 1 if Ker(a(i)) has a nonempty intersection with Ker(k), char_k(i) = 0 otherwise.
A property that this sequence shares with the Enots Wolley sequence is that when a new bit appears in the binary representation of a term for the first time, it must be as part of a number of the form 2^x + 2^y where 2^x < 2^y. In this situation, we say that 2^x is "introduced" by 2^y.
Theorem 2. If there are at least k distinct terms such that k is a candidate for a(i), k appears in the sequence.
Proof. If k is a candidate for a(i) but a(i) != k, either k has already appeared in the sequence and we have nothing to prove or there is some k' < k which is also a candidate. Since there are only k-1 positive integers less than k, this situation can occur at most k-1 times before k must be the lowest available candidate. QED.
Theorem 3. Every number with a binary weight of at least 2 appears in the sequence.
A proof is presented in the paper "The Binary Enots Wolley Sequence" by Nathan Nichols (see link).
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(1)=1 is the smallest possible value and does not lead to a contradiction.
a(2)=3=11_2 is the smallest value that satisfies the conditions. It does not lead to a contradiction.
a(3)=2=10_2 is the smallest value that satisfies the conditions, but then there is no choice for a(4). a(3)=6=110_2 is the next possibility, and does not lead to a contradiction.
a(4)=100_2 is the smallest value that satisfies the conditions, but then there is no choice for a(5). But a(4)=12=1100_2 works, and does not lead to a contradiction. (Examples added by N. J. A. Sloane, Mar 25 2022)
|
|
|
MAPLE
|
See Sloane link.
|
|
|
CROSSREFS
|
The Enots Wolley sequence: A336957.
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Edited, including a more precise definition. - N. J. A. Sloane, Mar 25 2022; corrected Apr 05 2022
|
|
|
STATUS
|
approved
|
| |
|
|
