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,2

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.

Links

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

Rémy Sigrist, PARI program for A275152

Example

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

Crossrefs

Cf. A235264, A275157.

Sequence in context: A130942 A082359 A266406 * A370794 A162371 A269856

Adjacent sequences: A275149 A275150 A275151 * A275153 A275154 A275155

Keyword

nonn,base

Author

Rémy Sigrist, Nov 13 2016

Status

approved