cp's OEIS Frontend

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.

%I A357578 #24 Oct 23 2022 23:53:41
%S A357578 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,
%T A357578 18,41,47,20,55,42,15,44,49,23,50,52,24,56,16,33,67,69,34,59,70,95,73,
%U A357578 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
%N 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.
%C A357578 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).
%C A357578 Theorem: For any k, the numbers in wc_k that appear in the sequence do so in their natural order.
%C A357578 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.
%C A357578 Conjecture: a(n) is a permutation of the positive integers.
%H A357578 Nathan Nichols, <a href="/A357578/a357578.png">Binary logarithm of the first 500000 terms</a>
%H A357578 Nathan Nichols, <a href="/A357578/a357578.txt">Binary digits of the first 250 terms</a>
%H A357578 Nathan Nichols, <a href="/A357578/a357578_1.txt">Binary digits of the terms surrounding the 81500th term where an unusual spike occurs</a>
%H A357578 Nathan Nichols, <a href="/A357578/a357578_2.txt">Binary digits of 1000 terms starting at n=23100. An example of more "typical" behavior of the sequence.</a>
%H A357578 Rémy Sigrist, <a href="/A357578/a357578.gp.txt">PARI program</a>
%e A357578 a(1)=1 and a(2)=2 are the initial conditions.
%e A357578 a(2)=3=11_2 because 3 is the least positive integer with a Hamming weight of 2.
%e A357578 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).
%o A357578 (PARI) See Links section.
%Y A357578 Cf. A000120.
%K A357578 nonn,base
%O A357578 1,2
%A A357578 _Nathan Nichols_, Oct 04 2022