A304749 -id:A304749 - cp's OEIS frontend

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.

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

Offset: 0

Antti Karttunen, May 03 2018, with more direct definition from David A. Corneth, May 05 2018

The original, but now conjectural, alternative definition is:
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.
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.
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.
From David A. Corneth, May 05 2018: (Start)
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.
Using this definition we can prove that 13 isn't in the sequence. (End)
The equivalence of these definitions is still conjectural. The official definition of this sequence follows the latter one. - Antti Karttunen, Jun 08 2018

Antti Karttunen, Table of n, a(n) for n = 0..26232
Index entries for sequences related to binary expansion of n

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

Cf. A303767 (a variant).

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 *)

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); };
v303769 = prepare_v303769(16384);
A303769(n) = if(!n,n,v303769[n]); \\ Antti Karttunen, Jun 08 2018

a(n) = A048675(A303762(n)). [The original definition, now conjectured]
For n >= 0, A007088(a(n)) = A304749(n).
From David A. Corneth, May 05 2018: (Start)
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).
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)

A304747 May code shown in binary: a(n) = A007088(A303767(n)).

Original entry on oeis.org

0, 1, 11, 10, 110, 100, 101, 111, 1111, 1000, 1001, 1011, 1010, 1110, 1100, 1101, 11101, 10000, 10001, 10011, 10010, 10110, 10100, 10101, 10111, 11111, 11000, 11001, 11011, 11010, 11110, 11100, 111100, 100000, 100001, 100011, 100010, 100110, 100100, 100101, 100111, 101111, 101000, 101001, 101011, 101010, 101110, 101100, 101101

Offset: 0

Antti Karttunen, May 23 2018

			The code can be constructed by the rule: a(n+1) is either the least number obtained from a(n) by toggling one or more 1-bits off 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 one 0-bit on:
   n    a(n)
   0      0
   1      1
   2     11
   3     10
   4    110
   5    100
   6    101
   7    111
   8   1111
   9   1000
  10   1001
  11   1011
  12   1010
  13   1110
  14   1100
  15   1101
  16  11101
  17  10000
  18  10001
  19  10011
  20  10010
  21  10110
  22  10100
  23  10101
  24  10111
  25  11111
  26  11000
  27  11001
  28  11011
  29  11010
  30  11110
  31  11100
  32 111100
  33 100000

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

Cf. A007088, A303767.

Cf. also A304749.

A209229(n) = (n && !bitand(n,n-1));
A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); }; \\ From A053644
A303767(n) = if(!n,n,if(A209229(n),n+A303767(n-1),A053644(n)+A303767(n-A053644(n)-1)));
A007088(n) = fromdigits(binary(n), 10); \\ From A007088.
A304747(n) = A007088(A303767(n));

a(n) = A007088(A303767(n)).

cp's OEIS Frontend

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula