Systematic survey of small patterns

[NickGotts]

Having generated and run 21,186,740 10-cell single-cluster patterns (out of an estimated 90,000,000), I have the first interesting result to report: a methuselah lasting 17,425 steps - thus beating bunnies10 by just 2 steps:

Code: Select all

x = 6, y = 6, rule = B3/S23
bo$2obo$4b2o$o2bo$o$o!

Step 30 of the pattern is almost the same as step 28 of bunnies10, but lacks a glider which the latter has just thrown off. It thus ends with a population of 1,744, including 40 gliders, as opposed to bunnies10's 1749 and 41 gliders. Since it's hardly a radical improvement, I suggest calling it bunnies10a. Its MCPS is 12, its bounding box 8*5.

Just to note what interesting results I could and could not find. Since my main aim is to find all 10-cell infinite growth patterns, I'm just looking at patterns that my algorithm does not judge to be quiescent at 16,384 steps. It's a conservative algorithm, since it just checks that the pattern contains nothing other than still lifes, oscillators, gliders and *WSSs, and requires the gliders and *WSSs to be a certain distance away from the still lifes, oscillators, and anything travelling in other directions. The version I'm using at present checks that the still lifes and oscillators are unchanged after 12 steps - so if an oscillator has a period not divisible by 12, the pattern is reported as non-quiescent. All such patterns reported so far either are or include a pentadecathlon, or are variants of bunnies10; but all the latter except bunnies10 itself and now bunnies10a, resolve in less than 17,423 steps.

I'll cross-post part of this message to the methuselahs thread.

[Moosey]

Just so that nobody ends up confused if they look at this thread and not the other,

Here's a 10-cell methuselah lasting 17,425 steps - thus beating bunnies10 by just 2 steps:

Code: Select all

x = 6, y = 6, rule = B3/S23
bo$2obo$4b2o$o2bo$o$o!

Step 30 of the pattern is almost the same as step 28 of bunnies10, but lacks a glider which the latter has just thrown off. It thus ends with a population of 1,744, including 40 gliders, as opposed to bunnies10's 1749 and 41 gliders. Since it's hardly a radical improvement, I suggest calling it bunnies10a. Its MCPS is 12, its bounding box 8*5.

A bit of background is available in the "Systematic survey of small patterns" thread.

I think you must have miscounted its lifespan— that IS bunnies 10

[NickGotts]

Just a note on why I estimate 90,000,000 10-cell single-cluster patterns. The numbers of single-cell patterns with successive numbers of cells are (using my algorithm for generating them) as follows, with ratios between the counts for successive numbers of cells, to three decimal places, added in parentheses:
o 1 cell: 0
o 2 cells: 0
o 3 cells: 10
o 4 cells: 66 (4:3 ratio 6.6)
o 5 cells: 551 (5:4 ratio 8.348)
o 6 cells: 5,777 (6:5 ratio 10.485)
o 7 cells: 61,898 (7:6 ratio 10.715)
o 8 cells: 692,809 (8:7 ratio 11.193)
o 9 cells: 7,870,790 (9:8 ratio 11.361)

As can be seen, the successive ratios increase, but the rate of increase shows a tendency to fall (although this is not quite monotonic). Multiplying 7,870,790 by 11.361 gives 89,420,045 (rounding down). So I expect the 10-cell count to be slightly above 90,000,000.

[NickGotts]

I managed to miscopy bunnies10a, posting bunnies10 instead. Thanks to moosey for catching the error on the Long-lived methuselahs thread. Here's the real bunnies10a:

Code: Select all

x = 8, y = 5, rule = B3/S23
2bo$ob2obo$6bo$o4b2o$7bo!

[praosylen]

Here's the real bunnies10a:

Code: Select all

x = 8, y = 5, rule = B3/S23
2bo$ob2obo$6bo$o4b2o$7bo!

Trivial variant with a smaller bounding box:

Code: Select all

x = 7, y = 5, rule = B3/S23
bo$3obo$5bo$o3b2o$6bo!

[NickGotts]

A for Awesome wrote:

Trivial variant with a smaller bounding box:
Code: Select all / Show in Viewer
x = 7, y = 5, rule = B3/S23
bo$3obo$5bo$o3b2o$6bo!

Thanks! Now you point it out, I find* it had actually turned up in my search a little earlier, only I didn't notice it, i.e., I failed to check exactly how long it lasted! With its smaller bounding box, it should clearly be the preferred variant.

*My generating algorithm generates all the patterns with a given distribution across columns together, and yours is a 2,2,1,0,2,2,1, which comes before 2,0,2,1,0,2,2,1 in the ordering I use, so I looked back to find that distribution.

[NickGotts]

This is not something that has yet turned up in my survey of single-cluster 10-cell patterns, but something I noticed should do so later. As far as oscillator periods are concerned, we know that 3 cells are required for period 2, 7 for period 3, and 8 for period 15. Turns out 10 are needed for period 8:

Code: Select all

x = 6, y = 6, rule = B3/S23
bo$2obo$4bo$bo$2bob2o$4bo!

I'd be surprised if no-one's noticed this before - probably just not thought worth noting, as my focus on minimal-cell starting pattern problems (mainly a result of their connection to sparse life) is unusual.

There may be period 4, 6 or 12 oscillators resulting from 9 or 10 cells - my searches would not turn them up as non-quiescent, as the test for quiescence I've used in these cases runs a pattern forward 12 steps for reasons of convenience (the factor of 4 makes it easy to identify gliders and *WSSs, the factor of 3 prevents pulsars giving a false positive for non-quiescence - at 8 cells and above, they become fairly common). There are no period n oscillators for any n that is not a factor of 12 produced from initial patterns with less than 10 cells. (A quibble here: if you count the whole final pattern, excluding gliders and *WSSs, as a single oscillator consisting of multiple independent parts, you could say there are period 6 oscillators starting from 8 cells (final patterns including a blinker and a pulsar), and period 30 oscillators starting from 10 cells (blinker plus pentadecathlon - the only 7-cell patterns producing a pulsar produce nothing else, the only 8-cell patterns producing a pentadecathlon produce nothing else).

Edit 2019-11-25: I originally wrote "9 cells" instead of "10 cells" in the last sentence. I only just noticed this error - one of two in the sentence; the other is corrected below.

[Sarp]

... the only 8-cell patterns producing a pentadecathlon produce nothing else).

Are you sure?

Code: Select all

x = 8, y = 6, rule = B3/S23
7bo$6b2o$2o$o$o$bo!

[2718281828]

... the only 8-cell patterns producing a pentadecathlon produce nothing else).

Are you sure?

Code: Select all

x = 8, y = 6, rule = B3/S23
7bo$6b2o$2o$o$o$bo!

I think he is. The only 8-cell pattern which produces only(!) the PD.

[NickGotts]

Sarp wrote:
Are you sure?
Code: Select all / Show in Viewer
x = 8, y = 6, rule = B3/S23
7bo$6b2o$2o$o$o$bo!

You're right of course - and in an earlier post, I described the 8-cell patterns that produce a pentadecathlon plus debris as well as those which produce a pentadecathlon alone - but managed to post the wrong rle (which 2718281828 quotes in the post after yours)! So apologies and thanks, here is the rle I should have posted on 12th December 2018:

Code: Select all

x = 65, y = 39, rule = Life
22bo$31bobo8bo$21b3o8bo8b3o$32bo3$32bo$21b3o8bo8b3o$31bobo8bo$22bo21$
2b3o27b3o28bo$bo2bo27bo2bo26b3o2$63bo3$2o28b2o$o29bo29b2o$60bo!

(I've discovered why I'm prone to post the wrong rle. The editor I use most of the time to look at rle files is a version of emacs which doesn't copy a selection to the clipboard when you hit Ctrl-C, as most of the software I use does. So if I'm not careful, I think I've copied the rle I want to include in a post, when I haven't.)

[NickGotts]

Here are two more variants of bunnies10a (10-cell single-cluster patterns that last 17425 steps). The one on the left has a bounding box 7*5, and an MCPS of 11, which according to the usual criteria for methuselahs makes it the preferred variant.

Code: Select all

x = 27, y = 5, rule = B3/S23
bo19bo$3o17b2obo$3bobo19bo$bo2b2o15b2ob2o$6bo19bo!

My search has also (as it should) found Paul Callahan's 10-cell single-cluster pattern producing a block-laying switch engine, together with 5 trivial variants:

Code: Select all

x = 50008, y = 50007, rule = B3/S23
bo$2obo$bobo$3bo$5bobo$5bo9995$10001bo$10000b2obo$10001bobo$10003bo$
10005bo$10005bobo9995$20001bo$20000b2obo$20003bo$20001bobo$20005bobo$
20005bo9995$30001bo$30000b2obo$30003bo$30001bobo$30005bo$30005bobo
9995$40001bo2$40000b2obo$40001bobo$40003bo$40005bobo$40005bo9994$
50001bo2$50000b2obo$50001bobo$50003bo$50005bo$50005bobo!

[Macbi]

Nice progress!

My search has also (as it should) found Paul Callahan's 10-cell single-cluster pattern producing a block-laying switch engine, together with 5 trivial variants:

Code: Select all

x = 50008, y = 50007, rule = B3/S23
bo$2obo$bobo$3bo$5bobo$5bo9995$10001bo$10000b2obo$10001bobo$10003bo$
10005bo$10005bobo9995$20001bo$20000b2obo$20003bo$20001bobo$20005bobo$
20005bo9995$30001bo$30000b2obo$30003bo$30001bobo$30005bo$30005bobo
9995$40001bo2$40000b2obo$40001bobo$40003bo$40005bobo$40005bo9994$
50001bo2$50000b2obo$50001bobo$50003bo$50005bo$50005bobo!

For those of us whose monitors are smaller than a parsec:

Code: Select all

x = 487, y = 479, rule = B3/S23
bo$2obo$3bo$bobo$5bobo$5bo93$96bo2$95b2obo$96bobo$98bo$100bo$100bobo
88$195bo$194b2obo$195bobo$197bo$199bo$199bobo93$290bo2$289b2obo$290bob
o$292bo$294bobo$294bo79$385bo$384b2obo$385bobo$387bo$389bobo$389bo93$
480bo$479b2obo$482bo$480bobo$484bo$484bobo!

[NickGotts]

Another slight improvement (in terms of number of life-span) to bunnies10. Let's call this one bunnies10b: lasts 17431.

Code: Select all

x = 9, y = 6, rule = B3/S23
o$bo$2bo$3bo$2b2obo$6b3o!

Bounding box 9*6, MCPS 11.

Here's an alternative form - the two have the same immediate successor:

Code: Select all

x = 9, y = 6, rule = B3/S23
o$2bo$bo$3bo$2b2obo$6b3o!

Same bounding box, but MCPS of 13.

Step 29 of bunnies10b is the same as step 23 of bunnies 10a.

I've now generated and tested 80,205,140 single-cluster 10-cell patterns. The original estimate of slightly over 90,000,000 in total still looks good.

[NickGotts]

The search of single-cluster 10-cell patterns is nearly done - I've generated and tested 85,844,356 patterns, and estimate the total is around 91,000,000. The search has turned up two more patterns that lead into a figure 8 to add to the one I noted in an earlier comment. I found another 5. but on close inspection all of these are two-cluster patterns by my definition. I gave myself a scare by not recognising this immediately - I thought the search had failed to find a pattern it should! Here are the 8 10-cell predecessors of the figure 8 - I think this is all, but I haven't proved that:

Code: Select all

x = 67, y = 68, rule = B3/S23
21bo$bo$2obo15bob2o$21bo$bo2bo19bo$3b2obo16b2obo2$4bo19bo14$bo$2obo15b
5o$4bo$bo$2bob2o16b5o$4bo15$41bo18bo$39bob2o16b2obo$63bo$41bo2bo15bo$
42bob2o16b2obo$63bo$44bo14$41bo19bo$39bob2o16bob2o$64bo$41bo2bo16bo$
43b2obo16b2obo$64bo$44bo!

The first that occurred to me (which has not yet turned up in the search, and should not yet have done so, but should do later) is first column, second row. The two the search just found are on the third row. The remaining 5 are two-cluster patterns, and so should not turn up in the current search; the one I mistakenly thought had been missed in the search is first column, first row.

[NickGotts]

The survey of single-cluster 10-cell patterns is complete, after 8 months. The total number of patterns generated and tested is 90465963 - right in line with my original estimate of just over 90 million. The only infinite growth patterns found are the one found by Paul Callahan in 1997, and the 5 trivial variants of this pattern I noted earlier. Several hundred patterns produced a pentadecathlon, alone or with other debris; 4 patterns produced a figure 8, in all cases alone (not 3 as I said above - I was misinterpreting my own cluster algorithm, the bottom right pattern in the collection posted above is counted as a single cluster). No other oscillators with period not a factor of 12 appeared. The search also resulted in a slight improvement in the longest-lasting 10-cell methuselah, as reported earlier. (Of course we could get two-cluster patterns that take longer to stabilise, just by putting the two clusters a long way from each other, but that applies as soon as we consider 8 cells.)

The sequence of numbers of clusters of increasing sizes, by the definition I've used, now goes: 0, 0, 10, 66, 551, 5777, 61898, 692809, 7870790, 90465963. The ratios between successive numbers (from 3 cells onwards) are (to 3 decimal places):
6.6
8.348
10.485
10.715
11.193
11.361
11.494
The second-order ratios (i.e. ratios between successive ratios) are:
1.265
1.256
1.022
1.045
1.015
1.012

There is a result covering the numbers of polyominoes showing that the corresponding first-order ratios approach a limit (Klarner (1967) "Cell Growth Problems", available online), which I imagine could be adapted to apply to this sequence, but no general way is known of calculating such limits. Anyhow, given the sequence so far, it looks as if there would be slightly over 1 billion 11-cell clusters - well beyond my current resources to generate and test.

Now, on to the two- and three-cluster 10 cell patterns!

[Sokwe]

Nice work! This is more of a comment than a request, but I would personally be interested to see the results of running each starting 9 and 10 cell pattern for exactly 12 generations to check for oscillators and spaceships of periods that are a factor of 12. I would not expect it to find anything new, but it would confirm that our list of oscillating objects up to 10 cells (56 still lifes, 7 p2 oscillators, and 2 spaceships) is complete. I think it's been previously confirmed that the list is complete at least for objects up to p4, but p12 is definitely still in question, and p6 probably is as well.

[NickGotts]

This is more of a comment than a request, but I would personally be interested to see the results of running each starting 9 and 10 cell pattern for exactly 12 generations to check for oscillators and spaceships of periods that are a factor of 12.

Thanks for your interest. I'd have to do something slightly more complicated than you suggest, as just running for 12 steps and checking for pattern identity would return all the period-2 and period-3 oscillators! I checked for non-quiescence after 16384 plus 12 steps to avoid finding all the patterns including pulsars, of which I'd expect there to be several thousand (and because it was a lot easier to account for gliders and XWSSs after a multiple of 4 steps). My aim in this survey is to find all the patterns with infinite growth (in turn, this is part of my long-term effort to understand Sparse Life); anything else coming to light is a bonus. But since generating the patterns took longer than running them all for 16,384 steps, then for another 12, and matching the two results, I'll consider doing as you suggest - at least for 9 cells - once I've finished checking the two- and three-cluster 10-cell patterns for infinite growth.

I also intend to make my code and data files available online at some point. However, the data files for 10 cell single-cluster patterns fill about 35GB, although I wouldn't necessarily need to include them all.

[Sokwe]

just running for 12 steps and checking for pattern identity would return all the period-2 and period-3 oscillators

p2 and p3 (and probably p4) oscillators and p2, p3, and p4 spaceships have already been enumerated up to 10 cells, so anything of those periods could just be discarded. I'm quite unsure about the search status of p6 oscillators and spaceships up to 10 cells, and I highly doubt p12 oscillators and spaceships have been searched up to 10 cells. However, I am confident that no such objects exist.

There may even be an easier way to enumerate all such patterns of periods 6 or 12, but I wouldn't know it. Most of the previous enumeration results were I think obtained by Heinrich Koenig.

I'll consider doing as you suggest - at least for 9 cells

Again, no pressure. It's just a little curiosity of mine to know what all of the small objects are.

once I've finished checking the two- and three-cluster 10-cell patterns for infinite growth.

I imagine the various combinations of two r-pentominoes and their 5-cell predecessors will make this tricky. Good luck!

[qqd]

10216M, a 10-cell methuselah consisting of two R-pentominos
Releases 24 gliders and 1 LWSS
Also temporarily produces a shillelagh

Code: Select all

x = 15, y = 3, rule = B3/S23
bo11bo$3o10b2o$o11b2o!