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
N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Nathan Nichols, Macaulay2 program
Nathan Nichols, The binary and decimal representations of the first 102 terms
Nathan Nichols, The Binary Enots Wolley Sequence, arXiv:2207.01448 [math.CO], 2022.
N. J. A. Sloane, Maple program (This includes a(0)=0, for compatibility with A252867)
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
KEYWORD
nonn,base
AUTHOR
Nathan Nichols, Nov 11 2020
EXTENSIONS
Edited, including a more precise definition. - N. J. A. Sloane, Mar 25 2022; corrected Apr 05 2022
STATUS
approved