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
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
KEYWORD
nonn,base
AUTHOR
Nathan Nichols, Oct 04 2022
STATUS
approved