[seqfan] Re: Sequence proposal by John Mason (by way of moderator)
john.mason at lispa.it
john.mason at lispa.it
Sun Aug 24 22:44:26 CEST 2014
Frank's "powers of 2" method certainly is an interesting alternative to my
prime number proposal.
The first few terms would be 1, 2, 7, 11, 15, 23, 27, 30, 75.
Even this method though requires an ordering to be defined, as merely
creating a sequence of ascending values will put some petrominoes before
the last tetromino. See therefore the ordering proposal in my original
mail.
John
> On 24 Aug 2014, at 19:38, "Frank Adams-Watters" <franktaw at netscape.net>
wrote:
>
> 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/
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list