|
| |
|
|
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
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
