[seqfan] Re: Sequence proposal by John Mason (by way of moderator)

[Frank Adams-Watters]

I've given some thought to representing polyominoes for inclusion in 
the OEIS. I've come up with two methods.

The first method is very similar to that proposed below by John. 
However, instead of populating the quarter-plane with primes, we use 
powers of 2; and then we add them, not multiply. So the monomio would 
be represented by 1, the domino by 2, and the trionimos by 7 and 11. 
Compared to the method proposed below, this will tend to keep values 
smaller. Note that it produces a pattern in the quarter-plane (not 
necessarily aligned nor a polyomino) for every non-negative integer. 
John's proposal only producing a (unique) pattern for square-free 
numbers. This could be fixed by labeling with numbers of the form p^2^k 
(A050376), but this is considerably less simple.

The second approach represents each polyomino with a short sequence of 
integers. Again, it involves pushing the polyomino into the corner, and 
then taking the smallest value for rotations and reflections. I will 
assume we are using 1,1 as our corner, not 0,0. (For both John's 
suggestion and the one above, it doesn't matter what corner we use, as 
long as the same one is used for labeling.) (It would be possible to 
use 0,0, but there is an irrational prejudice in favor of using the 
positive integers instead of the non-negative integers.) Now scan 
through the rows, generating a sequence of pairs of coordinates. So for 
the X or + pentomino, we get:

1,2; 2,1; 2,2; 2,3; 3,2

Now, as long as the pattern is a polyomino, and that the polyomino has 
at least been pushed up to row 1, Look what happens when we take the 
row numbers off:

2, 1, 2, 3, 2

The row numbers are now recoverable; the first row is 1, for subsequent 
points, if the column number is less than or equal to the previous 
column number, increment the row; otherwise leave it the same. This 
sequence of column numbers, then, is the representation of the 
polyomino.

One could go on to generate a binary number by putting a 1 and k-1 0's 
for a k in the sequence; the example above becomes 1011010010, or 722. 
This will change the ordering.

For the moment, I'm going to call John's proposal the factor method, my 
first proposal here the binary method, and the second proposal the 
column method.

The factor and binary methods have the disadvantage (IMO) that the 
first polyomino in a list is generically a triangle, with the last 
diagonal usually only partially filled:

OOOO
OOO
O

for example. The column method puts the straight-line polyomino first, 
which is what almost everyone does when enumerating polyominoes by hand.

Offsetting that, the fact that the column method produces a sequence 
instead of a single number is clearly a disadvantage.

One advantage of the binary method over the factor method is that it is 
easier to determine what pattern corresponds to a given number; binary 
decomposition is easier than factorization.

All three methods work equally well for fixed polyominoes (animals) or 
for one-sided polyominoes.

Certainly one disadvantage of the column method is that it does not 
work for general patterns. But it is elegant, the others are pretty 
much brute force approaches.

Franklin T. Adams-Watters

-----Original Message-----
From: Olivier Gerard <olivier.gerard at gmail.com>

From: john.mason at lispa.it

Dear Seqfans
I propose the following sequence for your consideration. As the
construction mechanism is rather arbitrary, I will quite understand if 
the
sequence is considered too specific for OEIS.

The sequence consists of those natural numbers that correspond to the
values of the numeric representation of free polyominoes as counted by
A000105. The representation of a polyomino is defined as follows:
1. Place the prime numbers on the Cartesian plain, putting 2 at (0,0), 
3 at
(1,0), 5 at (0,1), and so on, compiling the diagonals with successive
primes so as to form something like:
13,23, ...
 5,11,19, ...
 2, 3, 7, ...
(See also A078721)

2. Place a polyomino within the plane such that at least one square is
touching each axis.

3. Rotate and reflect the polyomino, respecting step 2, such that the
product of the primes covered by the polyomino has the minimum value. 
This
is the representation of the polyomino.

Hence the monomino has representation 2. The domino 6. The trominoes 30 
and
42.

Define the order of the sequence as follows – that all (n)ominoes come
before the (n+1)ominoes, and that within the (n)ominoes, the
representations shall be in ascending order. It is necessary to define 
the
order, as some (n+1)ominoes have representation less than some 
(n)ominoes.

The first terms of the sequence are therefore:
2, 6, 30, 42, 210, 330, 462, 714, 1155, 2310, 2730, 3570, 3990, 7854,
10626, 15015, 19635, 22134, 26565, 62238, 72105, 30030, 39270, 43890,
46410, 51870, 53130, 67830, 110670, 132090, 138138, 144210, 147630, 
149226,
180642, 243474, 255255, 257070, 324786, 336490, 420546, 451605, 456918,
608685, 1067154, 1142295, 1173102, 1174173, 1616615, 1742034, 1902318,
2667885, 2676234, 3136254, 4373358, 4755795

Some obvious consequences of the construction process:
1. The number of terms with n prime factors is equal to A000105(n).

2. The first term with n prime factors is at position sum(A000105(1), 
... ,
A000105(n-1))+1


john

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/