Page **1** of **1**

### n-cell thick patterns & infinite growth

Posted: **June 5th, 2009, 7:06 pm**

by **DivusIulius**

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**

by **DivusIulius**

**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**

by **Nathaniel**

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**

by **DivusIulius**

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**

by **Lewis**

Any results for the 4 x n patterns yet?

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

Posted: **June 16th, 2009, 3:30 am**

by **DivusIulius**

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**

by **Nathaniel**

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**

by **DivusIulius**

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**

by **Macbi**

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**

by **DivusIulius**

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**

by **Elithrion**

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**

by **Macbi**

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**

by **DivusIulius**

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**

by **Nathaniel**

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**

by **Macbi**

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.

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

Posted: **July 23rd, 2009, 9:15 am**

by **Nathaniel**

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.

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

Posted: **July 23rd, 2009, 10:45 am**

by **DivusIulius**

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**

by **Nathaniel**

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**

by **137ben**

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