# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a303769
Showing 1-1 of 1

%I A303769 #34 Jul 02 2018 07:00:07
%S A303769 0,1,3,2,6,4,5,7,15,14,12,8,9,11,10,26,24,16,17,19,18,22,20,21,23,31,
%T A303769 30,28,29,25,27,59,58,56,48,32,33,35,34,38,36,37,39,47,46,44,40,41,43,
%U A303769 42,106,104,96,64,65,67,66,70,68,69,71,79,78,76,72,73,75,74,90,88,80,81,83,82,86,84,85,87,95,94,92,93,89,91,123,122,120,112,113,97,99
%N A303769 a(0) = 0, a(n+1) is either the largest number obtained from a(n) by toggling a single 1-bit off (to 0) if no such number is yet in the sequence, otherwise the least number not yet in sequence that can be obtained from a(n) by toggling a single 0-bit on (to 1). In both cases the bit to be toggled is the rightmost possible that results yet an unencountered number.
%C A303769 The original, but now conjectural, alternative definition is:
%C A303769 a(0) = 0 and for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i which gives maximal value of A019565(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by toggling a single 0-bit of a(n-1) to 1. This is done by trying to toggle successive vacant bits from the least significant end of the binary representation of a(n-1), until such a sum a(n-1) + 2^h (= a(n-1) bitxor 2^h) is found that is not already present in the sequence.
%C A303769 The above construction is otherwise identical to that of A303767, except that we choose k_i with the maximal instead of minimal value of A019565.
%C A303769 In contrast to A303767, this sequence is not surjective (and thus not a permutation of nonnegative integers). The first missing term is 13 = A048675(70). See also comments in A303762, A303749 and A302775.
%C A303769 From _David A. Corneth_, May 05 2018: (Start)
%C A303769 Another description: a(0) = 0. a(n + 1) is the largest a(n) - 2^j > 0 that's not already in the sequence. If no such value exists, a(n + 1) is the least a(n) + 2^j not already in the sequence.
%C A303769 Using this definition we can prove that 13 isn't in the sequence. (End)
%C A303769 The equivalence of these definitions is still conjectural. The official definition of this sequence follows the latter one. - _Antti Karttunen_, Jun 08 2018
%H A303769 Antti Karttunen, <a href="/A303769/b303769.txt">Table of n, a(n) for n = 0..26232</a>
%H A303769 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A303769 a(n) = A048675(A303762(n)). [The original definition, now conjectured]
%F A303769 For n >= 0, A007088(a(n)) = A304749(n).
%F A303769 From _David A. Corneth_, May 05 2018: (Start)
%F A303769 The number of ones in the binary expansion of a(n) and a(n + 1) differ by 1. So A000120(a(n)) = A000120(a(n + 1)) +- 1. Furthermore, a(n + 1) <= 3 * a(n).
%F A303769 The number of binary digits of a(n + 1) is 0 or 1 more than the number of binary digits of a(n). So A070939(a(n + 1)) = A070939(a(n)) + 0 or 1. (End)
%t A303769 Nest[Append[#1, Min@ Select[{#2, #3, 2^IntegerLength[Last@ #1, 2] + Last@ #1}, IntegerQ]] & @@ Function[{a, d}, {a, SelectFirst[Sort@ Map[FromDigits[ReplacePart[d, First@ # -> 1], 2] &, Position[d, 0]], FreeQ[a, #] &], SelectFirst[Sort[#, Greater] &@ Map[FromDigits[ReplacePart[d, First@ # -> 0], 2] &, Position[d, 1]], FreeQ[a, #] &]}] @@ {#, IntegerDigits[Last@ #, 2]} &, {0}, 90] (* _Michael De Vlieger_, Jun 11 2018 *)
%o A303769 (PARI)
%o A303769 prepare_v303769(up_to) = { my(v = vector(up_to), occurred = Map(), prev=0, b); mapput(occurred,0,0); for(n=1,up_to, b=1; while(b<=prev, if(bitand(prev,b) && !mapisdefined(occurred,prev-b), v[n] = prev-b; break, b <<= 1)); if(!v[n], b=1; while(bitand(prev,b) || mapisdefined(occurred,prev+b), b <<= 1); v[n] = prev+b); mapput(occurred,prev = v[n],n)); (v); };
%o A303769 v303769 = prepare_v303769(16384);
%o A303769 A303769(n) = if(!n,n,v303769[n]); \\ _Antti Karttunen_, Jun 08 2018
%Y A303769 Cf. A000120, A019565, A048675, A302774, A302775, A303749, A303762, A304749 (terms shown in base-2).
%Y A303769 Cf. A303767 (a variant).
%K A303769 nonn,base
%O A303769 0,3
%A A303769 _Antti Karttunen_, May 03 2018, with more direct definition from _David A. Corneth_, May 05 2018

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE