A357578 Lexicographically earliest infinite sequence of distinct positive numbers with the property that a(n) is the smallest number not yet in the sequence with a Hamming weight equal to the Hamming weight of the XOR of previous two terms.

1, 2, 3, 4, 7, 5, 8, 11, 6, 13, 14, 9, 19, 21, 10, 31, 22, 12, 25, 26, 17, 28, 35, 63, 37, 38, 18, 41, 47, 20, 55, 42, 15, 44, 49, 23, 50, 52, 24, 56, 16, 33, 67, 69, 34, 59, 70, 95, 73, 74, 36, 61, 76, 27, 62, 81, 111, 79, 32, 119, 87, 64, 29, 91, 82, 40, 93, 94, 48, 103, 107, 65, 84, 88

Offset

1,2

Comments

Definition 1: Let wc_k (the k-th weight class) denote the set of positive integers with Hamming weight k. Let wc_k(i) denote the i-th member of the k-th weight class (in ascending order).

Theorem: For any k, the numbers in wc_k that appear in the sequence do so in their natural order.

A consequence of the theorem is that there exists an O(n) algorithm for computing a(n). This algorithm works by storing the least unused member of each weight class which has so far appeared in the sequence in an array. Using this information, it is possible to compute the n-th term from the previous (n-1) terms in O(1) time.

Conjecture: a(n) is a permutation of the positive integers.

Links

Table of n, a(n) for n=1..74.

Nathan Nichols, Binary logarithm of the first 500000 terms

Nathan Nichols, Binary digits of the first 250 terms

Nathan Nichols, Binary digits of the terms surrounding the 81500th term where an unusual spike occurs

Nathan Nichols, Binary digits of 1000 terms starting at n=23100. An example of more "typical" behavior of the sequence.

Rémy Sigrist, PARI program

Example

a(1)=1 and a(2)=2 are the initial conditions.
a(2)=3=11_2 because 3 is the least positive integer with a Hamming weight of 2.
a(3)=4=100_2 because s_2( a(2)^a(3) ) = 1, and 4 is the smallest positive integer with a Hamming weight of 1 not yet appearing in the sequence (since 1 and 2 already appear).

Prog

(PARI) See Links section.

Crossrefs

Cf. A000120.

Sequence in context: A026237 A308301 A373853 * A125150 A265901 A257801

Adjacent sequences: A357575 A357576 A357577 * A357579 A357580 A357581

Keyword

nonn,base

Author

Nathan Nichols, Oct 04 2022

Status

approved