Page 1 of 1

### n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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?

### Re: n-cell thick patterns & infinite growth

Posted: 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.

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.

### Re: n-cell thick patterns & infinite growth

Posted: June 16th, 2009, 2:59 am
Any results for the 4 x n patterns yet?

### Re: n-cell thick patterns & infinite growth

Posted: 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).

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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/

### Re: n-cell thick patterns & infinite growth

Posted: 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!

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.
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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.
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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.

### Re: n-cell thick patterns & infinite growth

Posted: 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.
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

### Re: n-cell thick patterns & infinite growth

Posted: 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!
``````