A275152 Sequence of distinct integers (considered as fixed disconnected 1-dimensional polyominoes and) chosen according to a greedy algorithm so as to tile a half line (see Comments for precise definition).

1, 2, 3, 4, 5, 8, 6, 7, 9, 11, 10, 13, 12, 14, 15, 16, 17, 19, 18, 20, 21, 25, 32, 22, 26, 23, 29, 24, 27, 33, 34, 37, 36, 40, 28, 30, 31, 35, 38, 41, 42, 45, 49, 48, 39, 43, 50, 57, 44, 52, 46, 53, 64, 47, 58, 51, 65, 68, 66, 54, 55, 72, 56, 59, 81, 61, 60

Offset: 1

Author

Rémy Sigrist, Nov 13 2016

Keywords

• nonn
• base

Comments

The indexes of the ones in the binary representation of a number give the positions of the squares in the corresponding polyomino. Thus:

- the number 1 = 2^0 corresponds to the monomino with a square at X=0,

- the number 2 = 2^1 corresponds to the monomino with a square at X=1,

- the number 13 = 2^0 + 2^2 + 2^3 corresponds to the (disconnected) tromino with squares at X=0, X=2 and X=3.

Shifting a polyomino dX squares to the right is equivalent to multiplying the corresponding number by 2^dX.

We use the following algorithm to generate this sequence:

- we start with a half (open) line of empty squares with coordinates X>=0,

- repeatedly, we choose the least number not yet used, such that the corresponding polyomino (possibly shifted to the right) (1) fills the current first empty square (2) and does not overlap one of the previously chosen polyominoes.

Occasionally, the partial tiling is perfect (i.e., all filled squares are contiguous); A275157 gives the corresponding indexes.

Examples

			The following table depicts the first terms, alongside the corresponding polyominoes ("X" denotes a filled square, "_" denotes an empty square):
n   a(n)  a(n) in binary  Corresponding shifted polyominoes
-   ----  --------------  --------------------------------
1   1     1               X
2   2     10              _X
3   3     11                XX
4   4     100               __X
5   5     101                  X_X
6   8     1000               ___X
7   6     110                    _XX
8   7     111                       XXX
9   9     1001                         X__X
10  11    1011                          XX_X
11  10    1010                             _X_X
12  13    1101                               X_XX
13  12    1100                                 __XX
14  14    1110                                    _XXX
15  15    1111                                        XXXX
		

Links

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

Crossrefs

Cf. A235264, A275157.