n-cell thick patterns & infinite growth

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

n-cell thick patterns & infinite growth

Post by DivusIulius » June 5th, 2009, 7:06 pm

I was wondering: How long is the minimum-length infinite-growing n-cell thick pattern for n=1, 2, 3, 4, 5? Paul Callahan's exhaustive search found the answers for n = 1 (i.e. 1 x 39) and n = 5 (i.e. 5 x 5) in 1997-1998. However, I am not sure if the results for n=2, 3, 4 have been published before.

I created a Perl script for Golly to find those patterns. Currently, I know the anwers for 2-cell thick patterns, and I have some preliminary results for 3-cell thick patterns.

http://infinitegrowth.wordpress.com/200 ... atterns-1/

TL;DR: there is only one 2-cell thick pattern that fits inside a 2 x 12 rectangle and produces a block-laying switch engine; there are at least two different 3-cell thick patterns that fit inside a 3 x 9 rectangle and produce a block-laying switch engine, and a glider-making switch engine, respectively.

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 6th, 2009, 9:42 am

Edit #1: Finally, there are twenty unique patterns with infinite growth inside a 3 x 9. All patterns are listed in the link above.

Edit #2: Pattern #15 is interesting because it produces a lightweight spaceship also.
Last edited by DivusIulius on June 10th, 2009, 8:50 am, edited 1 time in total.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: n-cell thick patterns & infinite growth

Post by Nathaniel » June 6th, 2009, 10:18 am

Have you exhausted the 3-by-8 rectangles? That is, do we know that 3-by-9 is minimal?

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 10th, 2009, 8:51 am

Yes, the script found no patterns with infinite growth inside any 3 x 8 rectangle.

Bugs are always possible, though. It would be nice if someone else tries to confirm these results. :P

Edit #1: If you find any counterexample inside a 3 x 8 it would be very much appreciated.

Edit #2: It's time for the 4 x n challenge. :wink:

User avatar
Lewis
Posts: 337
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

Re: n-cell thick patterns & infinite growth

Post by Lewis » June 16th, 2009, 2:59 am

Any results for the 4 x n patterns yet?

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 16th, 2009, 3:30 am

It seems that 4 x 7 is minimal.

Edit: Finally, there are thirty-one unique patterns that give rise to infinite growth (i.e. block-laying & glider-making switch engines).
Last edited by DivusIulius on June 21st, 2009, 7:14 pm, edited 8 times in total.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: n-cell thick patterns & infinite growth

Post by Nathaniel » June 16th, 2009, 8:38 am

DivusIulius wrote:It seems that 4 x 7 is minimal. At least there are sixteen unique patterns that give rise to infinite growth (i.e. block-laying & glider-making switch engines).

Still searching.
Cool beans, that means that the 2x12 pattern is the unique pattern that fits inside a bounding box of area 24 to exhibit infinite growth.

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 16th, 2009, 3:14 pm

Cool beans, that means that the 2x12 pattern is the unique pattern that fits inside a bounding box of area 24 to exhibit infinite growth.
Unnoticed result, LOL.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: n-cell thick patterns & infinite growth

Post by Macbi » June 16th, 2009, 3:29 pm

Nathaniel wrote:Cool beans, that means that the 2x12 pattern is the unique pattern that fits inside a bounding box of area 24 to exhibit infinite growth.
Yeah, nice insight.

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 22nd, 2009, 4:05 am

And so the minimal bounding boxes are:

1 x 39 (1 pattern) [double-checked]
2 x 12 (1 pattern)
3 x 9 (20 patterns)
4 x 7 (31 patterns) some of them even beautiful :)
5 x 5 (1 pattern) [also double-checked]

With regards to the 4 x 7 bounding box, you will find the 31 patterns at http://infinitegrowth.wordpress.com/200 ... atterns-2/

Lower bound minimal-bounding-box, where '(?)' means a conjecture:
6 x 5 (?)
7 x 4
8 x 4 (?)
9 x 3
10 x 3 (?)
11 x 3 (?)
12 x 2
13-38 x 2 (?)

Some additional results within each minimal bounding box were added also: specifically, the patterns with maximum final population that is NOT infinite.
http://infinitegrowth.wordpress.com/200 ... atterns-3/
Last edited by DivusIulius on June 23rd, 2009, 6:52 pm, edited 3 times in total.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: n-cell thick patterns & infinite growth

Post by Elithrion » June 22nd, 2009, 2:52 pm

Those aren't really conjectures, are they? If you can't have a 4x6 pattern, then by rotation, you can't have a 6x4 pattern; meanwhile, you can have a 5x5 pattern, which can clearly be contained in a 6x5 box, thus guaranteeing that 6x5 is minimal. The conjectures are thus trivially proven and their conjecture status should be withdrawn! :)
Vi veri veniversum vivus vici.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: n-cell thick patterns & infinite growth

Post by Macbi » June 22nd, 2009, 2:56 pm

I guess it's conceivable that there's no infinite growth pattern that's strictly 6*5, i.e. that 6*5 is the smallest box to go round it, rather than just a box that will.

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » June 22nd, 2009, 7:08 pm

you can have a 5x5 pattern, which can clearly be contained in a 6x5 box, thus guaranteeing that 6x5 is minimal
I guess it's conceivable that there's no infinite growth pattern that's strictly 6*5, i.e. that 6*5 is the smallest box to go round it, rather than just a box that will.
I agree. Let me rephrase what I wrote. :oops:

For example: with 6 x 5 (?) I meant: given the search space of 6 x n patterns (where height or width must be exactly 6 cells) what is the minimal n? Etc.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: n-cell thick patterns & infinite growth

Post by Nathaniel » July 23rd, 2009, 8:39 am

Upon looking through some old e-mail archives from 1998, it looks like these patterns have been studied before, but the results perhaps just not made available or particularly well-known. In particular, on October 13, 1998, Paul Callahan sent an e-mail containing the 2x12 pattern that you mentioned, noting that it was minimal for width-2 patterns. They had also discovered a 3x8 pattern that experiences infinite growth, but its minimality was not known.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: n-cell thick patterns & infinite growth

Post by Macbi » July 23rd, 2009, 9:03 am

Nathaniel wrote:They had also discovered a 3x8 pattern that experiences infinite growth, but its minimality was not known.
That contradicts:
DivusIulius wrote:
Nathaniel wrote:Have you exhausted the 3-by-8 rectangles? That is, do we know that 3-by-9 is minimal?
Yes, the script found no patterns with infinite growth inside any 3 x 8 rectangle.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: n-cell thick patterns & infinite growth

Post by Nathaniel » July 23rd, 2009, 9:15 am

Macbi wrote:
Nathaniel wrote:They had also discovered a 3x8 pattern that experiences infinite growth, but its minimality was not known.
That contradicts:
Ack! Whoops, sorry. I meant to say that they knew that no infinitely-growing pattern existed in a 3x8 bounding box, but they had not yet found a 3x9 infinitely-growing pattern. I somehow got it entirely backwards.

User avatar
DivusIulius
Posts: 89
Joined: April 1st, 2009, 11:23 am
Contact:

Re: n-cell thick patterns & infinite growth

Post by DivusIulius » July 23rd, 2009, 10:45 am

Predictably, what has been will be again, what has been done will be done again; there is nothing new under the sun...

I excel at wasting my time doing something that has already been done by other people, when I could be doing something more worthwhile. :wink:

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: n-cell thick patterns & infinite growth

Post by Nathaniel » July 23rd, 2009, 11:51 am

DivusIulius wrote:I excel at wasting my time doing something that has already been done by other people, when I could be doing something more worthwhile. :wink:
Meh, I still haven't seen mention of any of the 3x9 or 4-cell-wide patterns that you found, so I wouldn't call it wasted. And you certainly organized the info in a much easier-to-find way :P

137ben
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: n-cell thick patterns & infinite growth

Post by 137ben » February 6th, 2011, 10:12 pm

I propose a new challenge:
what is the smallest polyomino which contains as a subset a pattern that results in infinite growth? For example, the well-known 10 cell switch engine has size 14:

Code: Select all

x = 8, y = 6, rule = lifehistory
6.C$4.CD2C$4.C.C$3.DC$2.CD$CDC!
It is somewhat unnatural to measure the area of a pattern only using rectangular regions. And since the question of minimum initial population has essentially been solved, we might as well investigate non-rectangular bounding regions.

The best I can find seems to be the following 12 cell pattern with area 13:

Code: Select all

x = 9, y = 3, rule = B3/S23
7b2o$5bobo$3ob5o!

Post Reply