Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #22 Apr 03 2022 22:53:02
%S 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,
%T 29,24,27,33,34,37,36,40,28,30,31,35,38,41,42,45,49,48,39,43,50,57,44,
%U 52,46,53,64,47,58,51,65,68,66,54,55,72,56,59,81,61,60
%N 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).
%C The indexes of the ones in the binary representation of a number give the positions of the squares in the corresponding polyomino. Thus:
%C - the number 1 = 2^0 corresponds to the monomino with a square at X=0,
%C - the number 2 = 2^1 corresponds to the monomino with a square at X=1,
%C - the number 13 = 2^0 + 2^2 + 2^3 corresponds to the (disconnected) tromino with squares at X=0, X=2 and X=3.
%C Shifting a polyomino dX squares to the right is equivalent to multiplying the corresponding number by 2^dX.
%C We use the following algorithm to generate this sequence:
%C - we start with a half (open) line of empty squares with coordinates X>=0,
%C - 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.
%C Occasionally, the partial tiling is perfect (i.e., all filled squares are contiguous); A275157 gives the corresponding indexes.
%H Rémy Sigrist, <a href="/A275152/b275152.txt">Table of n, a(n) for n = 1..10000</a>
%H Rémy Sigrist, <a href="/A275152/a275152.gp.txt">PARI program for A275152</a>
%e The following table depicts the first terms, alongside the corresponding polyominoes ("X" denotes a filled square, "_" denotes an empty square):
%e n a(n) a(n) in binary Corresponding shifted polyominoes
%e - ---- -------------- --------------------------------
%e 1 1 1 X
%e 2 2 10 _X
%e 3 3 11 XX
%e 4 4 100 __X
%e 5 5 101 X_X
%e 6 8 1000 ___X
%e 7 6 110 _XX
%e 8 7 111 XXX
%e 9 9 1001 X__X
%e 10 11 1011 XX_X
%e 11 10 1010 _X_X
%e 12 13 1101 X_XX
%e 13 12 1100 __XX
%e 14 14 1110 _XXX
%e 15 15 1111 XXXX
%Y Cf. A235264, A275157.
%K nonn,base
%O 1,2
%A _Rémy Sigrist_, Nov 13 2016