A278388 Lexicographically earliest sequence such that (i*2^a(i)) AND (j*2^a(j)) = 0 for any distinct i and j (AND stands for the bitwise AND operator).

0, 0, 2, 2, 5, 7, 10, 3, 13, 14, 18, 20, 24, 27, 31, 10, 35, 36, 41, 34, 44, 48, 53, 55, 60, 64, 69, 72, 77, 81, 86, 15, 51, 42, 61, 89, 93, 95, 101, 102, 108, 109, 115, 119, 123, 128, 134, 136, 138, 143, 145, 149, 155, 160, 166, 169, 175, 180, 186, 190, 196

Offset: 1

Author

Rémy Sigrist, Nov 20 2016

Keywords

• nonn
• base

Comments

By analogy with A275152, this sequence can be obtained by the following algorithm:

- we start with a half-open line of empty squares with coordinates X=0, X=1, X=2, etc.,

- for n=1, 2, 3, ...: we choose the least k such that the polyomino corresponding to n, shifted by k squares to the right, does not overlap one of the previous polyominoes.

a(2*k+1) > a(2*k) for any k>0.

Examples

			The following table depicts the first terms, alongside the corresponding polyominoes ("X" denotes a filled square, "_" denotes an empty square):
n     n in binary    a(n)    n as a polyomino shifted by a(n) to the right
--    -----------    ----    ---------------------------------------------
1     1              0       X
2     10             0       _X
3     11             2         XX
4     100            2         __X
5     101            5            X_X
6     110            7              _XX
7     111            10                XXX
8     1000           3          ___X
9     1001           13                   X__X
10    1010           14                    _X_X
11    1011           18                        XX_X
12    1100           20                          __XX
13    1101           24                              X_XX
14    1110           27                                 _XXX
15    1111           31                                     XXXX
16    10000          10                ____X
17    10001          35                                         X___X
18    10010          36                                          _X__X
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A275152.

Programs

PARI

sumn2a = 0; for (n=1, 1 000, a=0; while (bitand(sumn2a, n<