A352574 -id:A352574 - cp's OEIS frontend

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.

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

Offset: 1

Nathan Nichols, Nov 11 2020

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).

			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)

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)

The Enots Wolley sequence: A336957.
Cf. A352571, A352572, A352573, A352574.
See also A000120 (binary weight), A252867.

Maple
```
See Sloane link.
```

Edited, including a more precise definition. - N. J. A. Sloane, Mar 25 2022; corrected Apr 05 2022

A352884 Binary weight of A109812(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 3, 1, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 4, 1, 3, 3, 2, 3, 3, 2, 3, 3, 2, 4, 2, 4, 2, 3, 3, 3, 3, 2, 4, 3, 1, 4, 3, 2, 4, 3, 2, 4, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 2, 4, 3, 3, 4, 2, 5, 2, 4, 2, 4, 3, 3, 4, 3, 4, 3, 3, 4, 3, 4, 3, 4, 3, 4, 3, 3, 4, 3, 3, 4, 3, 5, 1, 5, 3

Offset: 1

Antti Karttunen, Apr 07 2022

Equivalently, binary weight of A352575.

Antti Karttunen, Table of n, a(n) for n = 1..100000
Index entries for sequences related to binary expansion of n

Cf. A000120, A109812, A351963, A351964, A351965, A352889.

Cf. also A253589, A352791, A352574, A352575, A352576.

v109812 = readvec("b109812_to10e5.txt"); \\ Prepared from b-file data with gawk ' { print $2 } '
up_to = #v109812;
A109812(n) = v109812[n];
A352884(n) = hammingweight(A109812(n));

a(n) = A000120(A109812(n)) = A000120(A351965(n)).

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions