login
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

%I #84 Sep 05 2022 09:00:29

%S 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,

%T 40,52,22,67,41,28,68,65,27,30,100,97,129,130,26,29,37,96,74,15,53,80,

%U 192,131,23,44,104,81,133,38,42,73,69,54,56,136,132,39,43

%N 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.

%C This is an analog of the Enots Wolley sequence A336957 based on binary representations rather than prime factorizations.

%C 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}.

%C Theorem 1: For n > 2, a(n) is the smallest number m not yet in the sequence such that:

%C (i) Ker(m) intersect Ker(a(n-1)) is nonempty,

%C (ii) Ker(m) intersect Ker(a(n-2)) is empty, and

%C (iii) the set Ker(m) \ Ker(a(n-1)) is nonempty.

%C 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.

%C 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.

%C 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.

%C Theorem 2. If there are at least k distinct terms such that k is a candidate for a(i), k appears in the sequence.

%C 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.

%C Theorem 3. Every number with a binary weight of at least 2 appears in the sequence.

%C A proof is presented in the paper "The Binary Enots Wolley Sequence" by Nathan Nichols (see link).

%H N. J. A. Sloane, <a href="/A338833/b338833.txt">Table of n, a(n) for n = 1..10000</a>

%H Nathan Nichols, <a href="/A338833/a338833.txt">Macaulay2 program</a>

%H Nathan Nichols, <a href="/A338833/a338833_1.txt">The binary and decimal representations of the first 102 terms</a>

%H Nathan Nichols, <a href="https://arxiv.org/abs/2207.01448">The Binary Enots Wolley Sequence</a>, arXiv:2207.01448 [math.CO], 2022.

%H N. J. A. Sloane, <a href="/A338833/a338833_2.txt">Maple program</a> (This includes a(0)=0, for compatibility with A252867)

%e a(1)=1 is the smallest possible value and does not lead to a contradiction.

%e a(2)=3=11_2 is the smallest value that satisfies the conditions. It does not lead to a contradiction.

%e 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.

%e 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)

%p See Sloane link.

%Y The Enots Wolley sequence: A336957.

%Y Cf. A352571, A352572, A352573, A352574.

%Y See also A000120 (binary weight), A252867.

%K nonn,base

%O 1,2

%A _Nathan Nichols_, Nov 11 2020

%E Edited, including a more precise definition. - _N. J. A. Sloane_, Mar 25 2022; corrected Apr 05 2022