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

Author

Nathan Nichols, Oct 04 2022

Keywords

• nonn
• base

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.

Examples

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

Links

• 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

Crossrefs

Cf. A000120.

Programs

PARI

See Links section.