login
Smallest integers whose binary digits "1" define a polyomino if sorted into a quadrant shape.
2

%I #8 May 03 2016 12:52:47

%S 1,3,7,11,15,23,27,30,31,47,62,63,75,79,91,94,95,111,126,127,143,159,

%T 175,181,182,183,188,189,190,191,207,219,220,221,222,223,239,252,253,

%U 254,255,347,350,351,367,378,379,382,383,406,407,413,415,431,443,446

%N Smallest integers whose binary digits "1" define a polyomino if sorted into a quadrant shape.

%C Each integer k can be mapped onto a black-and-white checkerboard pattern if we read the digits of its binary representation into the diagonals of a quadrant form, the least-significant digit b(0) into the corner, taking 1, then 2, then 3 etc. digits to fill consecutive diagonals of the quadrant:

%C b(0) b(2) b(5) b(9) ..

%C b(1) b(4) b(8) ..

%C b(3) b(7) ..

%C b(6) ..

%C b(10)

%C This will leave one last diagonal partially filled unless the number of binary digits in k is a triangular number.

%C Replace the "1" bits by black unit squares and the "0" or unset bits by white squares.

%C If the black squares define a singly connected polyomino considering position and up-down-left-right connectivity, and if the same polyomino cannot be created by a number smaller than k, we add k to the sequence. Polyominoes are considered the same if they can be matched by translations, rotations or flips.

%e (i) The triangular representations of 3= 11, 5 = 101, 10=1010 and are

%e 1

%e 1

%e and

%e 11

%e 0

%e and

%e 00

%e 1

%e 1

%e The 1's define the same 2-omino in all 3 cases, so only the smallest representative, the 3, enters the sequence.

%e (ii) For k =181 = 10110101 the quadrant is filled with

%e 111

%e 01

%e 01

%e 0

%e No smaller number leads with this method to this T-shaped 5-omino, so 181 enters the sequence.

%e (iii) the representations of 6=110, 9= 1001 and 29 =11101 are

%e 01

%e 1

%e and

%e 10

%e 0

%e 1

%e and

%e 11

%e 01

%e 1

%e In all of these 3 cases, the 1's are not singly connected and do not represent polyominoes, so neither 6 nor 9 nor 29 can make it into the sequence.

%K nonn,base

%O 1,2

%A _Leonhard Kreissig_, Sep 06 2009

%E Explanation expanded - _R. J. Mathar_, Sep 22 2009