A303769 - OEIS

%I #34 Jul 02 2018 07:00:07

%S 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 30,28,29,25,27,59,58,56,48,32,33,35,34,38,36,37,39,47,46,44,40,41,43,

%U 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 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 The original, but now conjectural, alternative definition is:

%C 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 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 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 From _David A. Corneth_, May 05 2018: (Start)

%C 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 Using this definition we can prove that 13 isn't in the sequence. (End)

%C The equivalence of these definitions is still conjectural. The official definition of this sequence follows the latter one. - _Antti Karttunen_, Jun 08 2018

%H Antti Karttunen, <a href="/A303769/b303769.txt">Table of n, a(n) for n = 0..26232</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(n) = A048675(A303762(n)). [The original definition, now conjectured]

%F For n >= 0, A007088(a(n)) = A304749(n).

%F From _David A. Corneth_, May 05 2018: (Start)

%F 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 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 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 (PARI)

%o 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 v303769 = prepare_v303769(16384);

%o A303769(n) = if(!n,n,v303769[n]); \\ _Antti Karttunen_, Jun 08 2018

%Y Cf. A000120, A019565, A048675, A302774, A302775, A303749, A303762, A304749 (terms shown in base-2).

%Y Cf. A303767 (a variant).

%K nonn,base

%O 0,3

%A _Antti Karttunen_, May 03 2018, with more direct definition from _David A. Corneth_, May 05 2018