Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #13 Mar 03 2024 14:13:17
%S 0,1,2,3,4,5,7,8,6,9,11,15,16,10,14,17,12,13,18,19,23,31,32,20,21,29,
%T 34,24,25,27,36,26,30,33,22,40,41,43,47,63,64,28,35,39,55,72,37,45,61,
%U 66,44,46,62,65,38,54,73,48,49,51,59,68,42,58,69,50,76,77
%N Lexicographically earliest sequence of distinct nonnegative integers such that for any n >= 0, a(n) AND a(n+1) equals 0 or a(n) (where AND denotes the bitwise AND operator).
%C This sequence is a permutation of the nonnegative integers (with inverse A370794):- we can always extend the sequence with a power of 2 greater than any prior term,
%C - for any k >= 0, the first term >= 2^k is precisely 2^k,
%C - every power of 2 appears in the sequence, in ascending order,
%C - if a(n) = 2^k and the least value not in the sequence at this point, say v, satisfies v < 2^k, then a(n+1) = v, and eventually every nonnegative integer will appear in the sequence.
%H Rémy Sigrist, <a href="/A370793/b370793.txt">Table of n, a(n) for n = 0..10000</a>
%H Rémy Sigrist, <a href="/A370793/a370793.png">Scatterplot of the first 500000 terms</a>
%H Rémy Sigrist, <a href="/A370793/a370793.txt">C++ program</a>
%H Rémy Sigrist, <a href="/A370793/a370793_1.txt">C++ program (faster)</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e The first terms, alongside the bitwise AND of consecutive terms, are:
%e n a(n) a(n) AND a(n+1)
%e -- ---- ---------------
%e 0 0 0
%e 1 1 0
%e 2 2 2
%e 3 3 0
%e 4 4 4
%e 5 5 5
%e 6 7 0
%e 7 8 0
%e 8 6 0
%e 9 9 9
%e 10 11 11
%e 11 15 0
%e 12 16 0
%o (C++) See Links section.
%Y See and A109812, A303767 and A370790 for similar sequences.
%Y Cf. A370794 (inverse).
%K nonn,base
%O 0,3
%A _Rémy Sigrist_, Mar 02 2024