## n-cell thick patterns & infinite growth

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

### n-cell thick patterns & infinite growth

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.

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

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

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.

Nathaniel
Posts: 616
Joined: December 10th, 2008, 3:48 pm
Contact:

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

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

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

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

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.

Lewis
Posts: 326
Joined: March 17th, 2009, 5:26 pm
Location: UK
Contact:

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

Any results for the 4 x n patterns yet?

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

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

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.

Nathaniel
Posts: 616
Joined: December 10th, 2008, 3:48 pm
Contact:

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

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.

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

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

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.

Macbi
Posts: 735
Joined: March 29th, 2009, 4:58 am

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

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.

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

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

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

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.

Macbi
Posts: 735
Joined: March 29th, 2009, 4:58 am

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

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.

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

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

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.

Nathaniel
Posts: 616
Joined: December 10th, 2008, 3:48 pm
Contact:

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

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.

Macbi
Posts: 735
Joined: March 29th, 2009, 4:58 am

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

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.

Nathaniel
Posts: 616
Joined: December 10th, 2008, 3:48 pm
Contact:

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

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.

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

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

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.

Nathaniel
Posts: 616
Joined: December 10th, 2008, 3:48 pm
Contact:

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

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

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

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

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