Systematic survey of small patterns

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Systematic survey of small patterns

Post by NickGotts » November 28th, 2018, 7:47 am

This is the first of what is planned as a series of posts, about the systematic survey I’m doing of small Game of Life patterns (by which I mean, patterns with few cells). The main aims are first to confim the finding by Paul Callahan in 1997 that there are no infinite growth patterns with fewer than 10 cells; and second to catalog all those with 10 cells, confirming or refuting the hypothesis that all these develop into either block-laying or glider-stream switch engines. Simsim reported in 2014 (on the “23 cells quadratic growth (new record)” thread viewtopic.php?f=2&t=1483#p14143) having done a maybe-not-quite-complete search of 10-cell patterns consisting of two clusters (see below for my definition of a “cluster”), but no systematic survey of the single-cluster cases has been attempted as far as I know. I aim to cover every case and eventually, to produce a fully-documented account of what I’ve done – in effect, a proof that I have a complete enumeration of infinite-growth patterns with no more than 10 cells, although it’s unlikely to come up to the standards of rigour a mathematics journal would require. This is all in the service of the investigation of “Sparse Life” (infinite fields of arbitrarily low initial density) that I’ve pursued on and off since the 1970s, and am now resuming after a long break. I’m working in Python 2.7, with the actual pattern runs performed in Golly. I have Python code to check whether a pattern is “quiescent”, meaning it consists only of still-lifes, oscillators, gliders and *WSSs which will not interact in future. The code would mark patterns containing any other kind of spaceship as non-quiescent, and also requires a “period” parameter, which tests whether the non-spaceship part of the pattern is the same after a set number of steps; hence patterns containing oscillators of periods that are not factors of this parameter would be marked non-quiescent. All patterns marked as non-quiescent are therefore checked to see why they have been so marked. Varying the period, and some aspects of the code, allow for searches for outcomes other than infinite growth (oscillators of different periods, gliders, *WSSs).

A cluster, by the definition I’m working with, consists of one or more polyplets. A polyplet is a set of on-cells connected orthogonally or diagonally, so that there’s a path between any two on-cells (when I refer simply to the “cells” of a pattern I mean the on-cells; I’ll only use the latter term when needed for clarity) that goes through no off-cells. If there is more than one polyplet, then adding all the off-cells that both border more than one polyplet, and have at least three on-cell neighbours, must produce a single polyplet. Thus by this definition, two separate clusters may share a common neighbouring off-cell (or for larger clusters, more than one such neighbour), as long as none of these neighbours itself has three on-cell neighbours. Additionally, every on-cell in the whole cluster must belong to at least one 3*3 square of cells containing at least 3 on-cells (this condition excludes some groups that would otherwise meet the definition, but include a 2-plet where only one of the cells is in such a 3*3 square; the other member of the 2-plet could then be removed without changing the successor pattern).

For the purpose of checking for any infinite growth patterns of less than ten cells, it makes sense to check smaller patterns first, so the search is divided into a series of sub-searches checking 3, 4, 5…9 cell patterns, I’ve currently completed work on the patterns up to 8 cells – and of course found no infinite growth, but have some findings to report in a later post (apart from the main aims, I’ll also report on any interesting findings along the way). I have catalogued all the 9-cell single-cluster patterns, but not yet run them, and done preliminary work for the two- and three-cluster 9- and 10-cell patterns. Taking this approach, we need only consider patterns that grow at step 1 (I use the term “step” where some prefer “generation”): any that reduce their cell-count (number of on-cells) at step 1 will already have been checked, and any that remain at the same cell-count must lead, possibly through a chain of successors with the same cell-count, to a pattern with either decreased or increased cell-count. If the former, the successor with decreased cell-count will already have been checked; if the latter, it will be found in the current sub-search. In the ten-cell case, since I want a full enumeration of infinite-growth patterns, ten-cell patterns with ten-cell successors will need to be checked. Also, for two- and three-cluster patterns, it is only failure of the total cell-number to grow at step 1 that automatically eliminates a pattern: one or (in the twin-cell case) even two clusters may shrink while the total grows.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » November 28th, 2018, 8:01 am

I should say that I’m pretty confident of Paul Callahan’s result, but he said himself that additional checks that all cases were covered would be good. The best way to check a result which relies on relatively complex program design and coding is for it to be redone using a different language and algorithm! I will also, as noted in the preceding post, report interesting findings along the way.

The numbers of polyplets up to 10 cells (not counting rotations and reflections) is given at https://oeis.org/A030222 as:
1, 2, 5, 22, 94, 524, 3031, 18770, 118133, 758381.
The numbers of clusters, by the definition in the preceding post, up to 9 cells, are (again, excluding rotations and reflections):
0, 0, 10, 66, 551, 5777, 61898, 692809, 7870790.
As can be seen, the ratio of the number of clusters to the number of polyplets increases quite fast. Judging by the way the numbers increase, I estimate there to be about 90000000 10-cell clusters. Looser definitions of a cluster would not only increase the numbers, but include cases where one or more on-cells could be removed without changing the immediate (step 1) successor pattern – and my hunch is that the proportion of these would grow rapidly with the number of cells.

I won’t describe my algorithm for generating the clusters yet; commented code is the appropriate medium for that. I am reasonably confident it is correct; I have been able to check that the number of polyplets it generates is right (and they include no duplicates) – the algorithm does not work by generating polyplets then combining them. Up to 6 cells, more extensive checks have been done.

Up to five cells, only single-cluster patterns need be considered, as single on-cells and isolated pairs vanish on step 1. From six cells upwards, pairs of clusters that interact at some point must be taken into account (obviously, if the two never interact, the whole pattern will grow indefinitely, or produce anything else of interest, only if one of the clusters does). For six on-cells, two separate 3-clusters (a 3-3 pattern) can interact after step 1 or 2 (they must become a single cluster to do so†), but if they do not do so then, they never will. For seven on-cells, combinations of a 4-cluster and a 3-cluster (4-3 patterns) must be examined, and the two clusters may take up to 12 steps before interacting, if the 4-cluster is a traffic light predecessor. It might be thought that only the blinker and preblock need be considered among the 3-clusters, but it is possible for other 3-clusters, which leave fewer than 3 on-cells at step 1 and would vanish at step 2, to interact with the successor of a 4-cluster that was initially separate. With eight initial on-cells, there are 4-4 and 5-3 patterns. Among the latter, if the 5-cell cluster is or becomes a glider or particularly an r-pentomino, new complications arise, since either can eventually interact with an arbitrarily distant blinker or preblock. In this sense there are an infinite number of 5-3 patterns to consider, and they may take any number of steps to resolve; but in fact once a certain distance between the initial glider or r-pentomino and the 3-cell cluster is reached, the only differences in the result are the distances between the resulting oscillators, gliders, and other spaceships.

With nine cells, there are 6-3, 5-4 and 3-3-3 patterns; and with ten, 7-3, 6-4, 5-5 and 4-3-3 patterns. The 5-5s produce new complexities as both may be gliders or r-pentominos; and there is a tricky point about the 4-3-3s. It might be thought they can be dealt with simply by starting with all the 4-3s where the 4 and 3 interact and adding another 3, but in fact the 4 may be too far from both 3s to interact with either if the other were not present, while with both present it interacts with the result of their interaction. Given this, we might wonder if a similar complication arises with 3-3-3 patterns, such that no pair would ever interact without the third being present. This does not seem to be the case, and it can be shown that if there are any such cases, they do not need to be taken into account when looking to rule out infinite growth for nine-cell patterns. For a 3-3-3 pattern to grow at step 1, at least one of the clusters must be a preblock. But there are only four cells which another cluster could occupy that have a common off-cell neighbour with a block (as the preblock will become at step 1), without becoming part of the same cluster: the cells at the corners of a 6*6 square with the block at the centre. But if the two other 3-cell clusters occupy two of these, the pattern will still remain three separate clusters, and will reach quiescence at step 2.

†I will say that two or more initially separate clusters interact if and when clusters descended from them form part of the same cluster. This allows for cases where one or both of the original clusters split at or before that point. It includes cases where the history of the two or more subclusters of the new cluster is in fact unaffected, as for example when two blocks form simultaneously on the same rows and with a single column between them, so that the neighbouring off-cells they share all have either two or four on-cell neighbours.

User avatar
gameoflifemaniac
Posts: 1242
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Systematic survey of small patterns

Post by gameoflifemaniac » November 28th, 2018, 11:11 am

How do you define a cluster?
I was so socially awkward in the past and it will haunt me for the rest of my life.

Code: Select all

b4o25bo$o29bo$b3o3b3o2bob2o2bob2o2bo3bobo$4bobo3bob2o2bob2o2bobo3bobo$
4bobo3bobo5bo5bo3bobo$o3bobo3bobo5bo6b4o$b3o3b3o2bo5bo9bobo$24b4o!

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Systematic survey of small patterns

Post by wildmyron » November 28th, 2018, 11:41 am

gameoflifemaniac wrote:How do you define a cluster?
The second paragraph of the first post contains the definition of a cluster.

To NickGotts: Thank you for sharing the details of your search/ survey. I'm looking forward to reading about your results
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » November 28th, 2018, 7:50 pm

Thanks wildmyron.

I realise there is a slight oddity about my definition of a "cluster": it means that some patterns do not consist just of one or more clusters - for example, any that include isolated single cells or pairs of cells since, as defined, these are not clusters. But in a search for the smallest number of on-cells necessary to produce infinite growth (or many other outcomes), only clusters as I have defined them need be considered. For any pattern including non-clusters with the property of producing outcome X, there will be a smaller (lower cell-count) pattern which shares that property, produced simply by removing some cells that make no difference to the pattern produced at step 1. We could regard "cluster" as shorthand for "cluster-of-interest-in-cell-count-minimization-problems".

A brief word about "Sparse Life", which lies behind my interest in this class of problems. Very early in the history of Game of Life, the question was raised "What happens in infinite random fields?". This was asked most often of fields with an initial density of 50%, and of fields with arbitrarily low density - "Sparse Life". One way to think about analysing such fields is to say: "What happens in an infinite random field as the probability p of each cell being on initially, approaches 0" (without of course actually reaching it). In other words, whenever in the analysis, a question comes up which would have different answers depending on whether p is above or below a certain non-zero value, we assume it is below that value. In Sparse Life, initial clumps of n cells (I'm deliberately using a vaguer term than "cluster" here, just meaning a group of cells within some specified distance of each other) are always more common, by a factor on the order of 1/p, than clumps of n+1 cells. Hence, for the dynamics of Sparse Life, cell-count minimisation problems are basic to the analysis. Things get a lot more complicated when the interactions between initially distant clumps are considered, but the lowest cell-count needed for infinite growth, and also for infinite growth where the pattern's cumulative image (the set of cells that were on at some time in its history) grows faster than linearly, turn out to be of key significance. The cumulative image of both block-laying and glider-stream switch engines grows linearly, like the number of cells in the pattern itself, while the cumulative image of rakes typically grow quadratically, even when the number of cells increases only linearly.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » November 29th, 2018, 1:53 pm

Here's the first post that reports an interesting finding. (Interesting to me, anyway!) I've always considered "Methusalehs" a rather ill-defined and artificial category of pattern. The definition in the wiki (http://www.conwaylife.com/wiki/Category:Methuselahs) is:
A methuselah is a pattern that takes a large number of generations in order to stabilize (known as its lifespan) and becomes much larger than its initial configuration at some point during its evolution.
,
but additional qualifications tend to be added. Indeed, they have to be, since "larger" is ambiguous (diameter? bounding box? cell-count? something else?). Anyhow, the 8-cell pattern with the longest time to stability as listed in the wiki (http://www.conwaylife.com/wiki/List_of_ ... ethuselahs) is 7468M, which by an odd coincidence takes 7468 steps to stabilise. An eight-cell pattern which takes longer to stabilise can be constructed just be setting a glider on a path to hit an arbitrarily distant preblock or blinker, but if we insist that the pattern must not consist of separate parts that all stabilise before they interact, can we do better than 7468. Yes, in the words of a well-known American statesperson, we can!

Code: Select all

x = 220060, y = 65, rule = B3/S23
40002b2o60018b2o19978b2o30001b2o19995b2o$2o9998b2o9998b2o9999b2o9998bo
10012b2o10009b2o10000b2o9971b3o9997b3o10018bo9982b3o9994bo10032b3o
10009b3o9955bo10001bo9994bo10017bo10003bo10008bo10021bo10004bo$o9999bo
9999bo10000bo9999bo10012bo10010bo10001bo29993bo19979bo30002bo10001bo
9994bo10017bo10003bo9978b2o28bo10021bo10004bo$40001bo60019bo19979bo
30002bo10001bo9994bo10017bo10003bo9977bo30bo10021bo10004bo$200001bo$
20b2o199979bo$19bo179982b2o$19bo59982b2o49998b2o69997bo$19bo59981bo
49999bo69999bo$60001bo49999bo69999bo$60001bo49999bo5$170010bo$40008b2o
130000bo$40008bo130001bo5$90030b2o$90029bo$90029bo$90029bo6$160002b2o$
160001bo$160001bo$20014b2o139985bo$20013bo$20013bo$20013bo60046b2o$
80059bo$10017b2o19983b2o50055bo19940b3o$10016bo19984bo50057bo69940bo$
10016bo19984bo119998bo$10016bo19984bo119998bo2$70002b2o$70001bo50007b
3o$50002b2o19997bo$50001bo19999bo$50001bo80000b2o9998b2o$50001bo79999b
o9999bo79999bo$130001bo9999bo79999bobo$130001bo9999bo79998b2o2$190002b
2o$190001bo$190001bo$190001bo5$210002b2o$210001bo$210001bo$210001bo!
The rle above shows 23 eight-cell patterns which take more than 8192 steps (I tend to use powers of 2) to stabilise. Each consists of an r-pentomino grandparent (the one at the extreme right has a different grandparent from the others) and a preblock or blinker. Either grandparent would do in each case, and any of the six r-pentomino parents, or the r-pentomino itself, could be substituted while losing one or two steps from the time to stability. The eight patterns at the left include a preblock, and obviously any of the four orientations of preblock would do. So these 23 patterns represent 9*47=423 eight-cell patterns that have not stabilised by step 8192, or 3384 including rotations and reflections, since none of the 423 have any symmetries. The longest lifetime is that of the seventh from the right, which stabilises at step 14321, with a population of 1730, including 39 escaping gliders.

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Systematic survey of small patterns

Post by dvgrn » November 29th, 2018, 4:24 pm

NickGotts wrote:Here's the first post that reports an interesting finding. (Interesting to me, anyway!)
...
The rle above shows 23 eight-cell patterns which take more than 8192 steps (I tend to use powers of 2) to stabilise.
Huh, so these methuselahs fall into an apparently unsearched gap between the space of all 8-cell single clusters (Tomas Rokicki's search from 2005, which found 7468M as the longest-lasting methuselah in that category) and the space of all 8-cell Patterns That Can't Be Subdivided Into Two Or More Parts That All Stabilize Separately Before Interacting.

(A shorthand word might be good to have, for that second category...)

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Systematic survey of small patterns

Post by Freywa » November 29th, 2018, 7:24 pm

dvgrn wrote:Huh, so these methuselahs fall into an apparently unsearched gap between the space of all 8-cell single clusters (Tomas Rokicki's search from 2005, which found 7468M as the longest-lasting methuselah in that category) and the space of all 8-cell Patterns That Can't Be Subdivided Into Two Or More Parts That All Stabilize Separately Before Interacting.

(A shorthand word might be good to have, for that second category...)
How about indecomposable 8-cell patterns?
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Systematic survey of small patterns

Post by dani » November 30th, 2018, 2:33 am

The longest lasting pattern there is this, 14321M:

Code: Select all

x = 6, y = 34, rule = B3/S23
5bo$5bo$5bo28$b2o$o$o$o!
It even has a mango in its ash!

'Indecomposable' sounds a bit iffy, I like 'nondecomposable' better, it's in wiktionary...

Gamedziner
Posts: 795
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Systematic survey of small patterns

Post by Gamedziner » November 30th, 2018, 7:18 am

danny wrote:The longest lasting pattern there is this, 14321M:

Code: Select all

x = 6, y = 34, rule = B3/S23
5bo$5bo$5bo28$b2o$o$o$o!
It even has a mango in its ash!
It actually has two mangoes, one at (3494,3557) and the other at (3514,3663).

Code: Select all

x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » November 30th, 2018, 7:51 am

Thanks for the suggestions! Another possible term for patterns that do consist of parts that start separate, all become stable, then interact (via gliders or other spaceships) is zombies, unless that term is already in use. So patterns that aren't of this type would be non-zombies. In any case, if the patterns I reported (they must have been found during Paul Callahan's search but not been reported, I think) are challenged as methusalehs, I can point out that the wiki's list of methusalehs already contains similar multi-part (but non-zombie/nondecomposable/indecomposable) patterns, for example 40514M http://www.conwaylife.com/wiki/40514M.

Incidentally, by the definition I've used, 7468M consists of two separate clusters.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 4th, 2018, 7:21 am

I have now finished surveying single-cluster 9-cell patterns. Nothing of special interest appeared. The longest-lasting methusalehs led to the same endpoint as Bunnies 9, but in slightly fewer steps. The two- and three-cluster patterns may take a while, but meanwhile I am preparing a couple of posts on cell-count miimization problems.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 4th, 2018, 8:24 am

This post is about “velocity classes” in small patterns. Any non-infinite growth pattern that has become stable (stability is quite hard to define in general for infinite growth cases), can be classified according to the set of “velocity classes” the functionally separate parts (i.e. clusters or sets of clusters that will only interact with others within the set) belong to. By a “velocity class” I just mean all the separate parts that are moving across the LIfe field in the same direction and with the same speed (still lifes and oscillators belong to the zero-velocity class).

For one and two cell patterns, the set of final velocity classes is of course empty for all patterns. For all three and four cell patterns, the set is either empty, or consists only of the zero-velocity class, which I’ll call ZV. For five cells, in addition to these possibilities, the set may consist of {45:c/4} – the glider, or {ZV, 45:c/4, 135:c/4, 225:c/4} – the r-pentomino. By 45:c/4 I mean travel at 45 degrees clockwise from some chosen orthogonal direction at speed c/4, by 135:c/4 travel at the same speed at 135 degrees clockwise to that reference direction, and so on. To avoid ambiguity, I’ll always list the non-zero velocity classes so the lowest numbers possible are used early in the listing of the set. So, if gliders are escaping but there are no orthogonal spaceships, 45:c/4 will always appear, if gliders are going in two directions but there are no spaceships 45:c/4 and either 135:c/4 or 225:c/4 will appear; but if there is for example an escaping LWSS, 0:c/2 will begin the list or immediately follow ZV, and even if there are gliders as well, 45:c/4 might not appear, as they may all be travelling at an angle of 135 degrees to the LWSS. If I illustrate with a pattern, I will rotate andor reflect it if necessary (with direction 0 being chosen as north or upward). As should be obvious, if n-cell patterns allow a given set of final velocity classes, so do all larger numbers of cells, if only by adding single cells too far away to make a difference (note that I’m allowing all patterns here, not excluding isolated cells or parts that never interact).

So with 1 cell (or 0 cells), we have:
{}

With 3 cells, add:
{ZV}

With five cells, add
{45:c/4}
{ZV, 45:c/4, 135:c/4, 225:c/4}

With six cells, add:
{ZV, 45:c/4} (This is the block and glider.)
{ZV, 45:c/4, 135:c/4} (This is the Herschel, among others.)

With seven cells add:
{45:c/4, 135:c/4}
{ZV, 45:c/4, 225:c/4}
{ZV, 45:c/4, 135:c/4, 225:c/4, 315:c/4}

All these are illustrated by examples in the rle shown below, where patterns starting with more cells are shown further down. Seven cells is as far as I have made a comprehensive check of all possibilities (doing so this far was a byproduct of the search for infinite growth patterns with up to 10 cells, going on to check all possibilities for eight or more cells would require significant additional work – I may come back to it). However, I have found an 8-cell pattern which exemplifies the set {45:c/4, 225:c/4}, also shown. That leaves only two sets involving only static debris and gliders: {45:c/4, 135:c/4, 225:c/4} and {45:c/4, 135:c/4, 225:c/4, 315:c/4} – gliders going in three or all four directions, with no static debris. The former can certainly be done with 12 cells: the 7-cell {ZV, 45:c/4, 135:c/4} pattern plus a glider; and the latter in 14, by combining two of the 7-cell patterns in different orientations. These are shown as well.

Code: Select all

x = 8007, y = 28005, rule = Life
o4000$o$o$o3998$3o3997b2o$2bo3999bo$bo4000bo$4002bo3997$o3999bo$o4000b
2o$ob2o3999b2o$bo4000bo3997$obo3997bobo3998bo2b3o$bo3999bo3998bo2bo$bo
4000bo3998bo$b2o4000b2o$o4004bo3996$3o$3bo$bo$2b3o3997$3o2bobo$o5bo$bo
4bo$6b2o$5bo3996$obo3bobo$bo5bo$bo5bo$2o5b2o$2bo3bo!
With eight cells or more, of course, additional velocity classes are possible, as *WSSs can be produced. I will deal with those in a separate post, as there are three different types of *WSS (LWSS, MWSS, HWSS) to consider, as well as more complex spaceships with the same velocity.

hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: Systematic survey of small patterns

Post by hkoenig » December 4th, 2018, 12:14 pm

One minor comment:

Since all velocities will be integer ratios, you might want to use that instead of angle in degrees, to avoid future problems specifying knightship velocities.

Or, since all known small spaceships travel in only 8 directions, maybe a compass rose (N, NE, etc) or even radians with the (pi/4) implied.

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Systematic survey of small patterns

Post by 2718281828 » December 4th, 2018, 6:31 pm

I very much like the effort on analysing small pattern in detail.

I had in mind that either the single cluster pattern (maybe also the polyplets) with a certain number of cells are very suitable for a survey on the frequency of 'naturally occurring' methuselahs/induction coils.

As an id for a methuselah I suggest the pattern with maximum population (until time to stability), in case of a tie - just breaking it e.g. by the first occurring maximum, then the pi has e.g. this representative pattern:

Code: Select all

x = 39, y = 24, rule = B3/S23
19bo$12b2o5bo5b2o$14bo4bo4bo$4b2o27b2o$3bobo6b2obo7bob2o6bobo$4bo8bob
2o5b2obo8bo$12b2o11b2o$12b2o11b2o$6bo5b2o11b2o5bo$5b3o8bo5bo8b3o$4bobo
bo3bob2o7b2obo3bobobo$4bo3b4ob4o5b4ob4o3bo$2b2o6b2o2bob2o3b2obo2b2o6b
2o$bo4bo4bob5o3b5obo4bo4bo$3o2bobo4b2obob2ob2obob2o4bobo2b3o$bo4bo3b2o
3bob2ob2obo3b2o3bo4bo$2b2o5b2o2bo3b2ob2o3bo2b2o5b2o$4bo3bo7bo5bo7bo3bo
$4bobobo7bo5bo7bobobo$5b3o3bo15bo3b3o$6bo6bo11bo6bo$10b2o15b2o$10b2obo
11bob2o$12b2o11b2o!
In contrast to the ash, this allows to classify also methuselahs, like die-hard

Code: Select all

x = 8, y = 3, rule = B3/S23
6bo$2o$bo3b3o!
with the identifying pattern:

Code: Select all

x = 10, y = 13, rule = B3/S23
3b2o2$bo2$obobo$b4o$b2o$2b4o2b2o$2b2ob2o2bo$b3o2b3o$bo2b4o$bo2b2o$2b3o
!
Further, it allows to avoid the problem with different early stage starting pattern which evolve to the same methuselah. E.g. both pattern:

Code: Select all

x = 15, y = 4, rule = B3/S23
13bo$3o9bobo$obo9bobo$obo9bobo!
would could called pi.

I analysed them a bit on my 3 glider collisions, but this is not really representative for naturally occurring.
But I as mentioned such an analysis for single cluster pattern (or polyplets) would be great.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 10th, 2018, 12:21 pm

hkoenig says:
Since all velocities will be integer ratios, you might want to use that instead of angle in degrees, to avoid future problems specifying knightship velocities.

Or, since all known small spaceships travel in only 8 directions, maybe a compass rose (N, NE, etc) or even radians with the (pi/4) implied.
Good point. After a lot of thought, I've come up with two descriptive schemas for velocities - one comprehensive, covering knightships etc., the other more readable, covering gliders and *WSSs. Here’s a revised version of the post on velocity classes:

This post is about “velocity classes” in small patterns. Any non-infinite growth pattern that has become stable (stability is quite hard to define in general for infinite growth cases), can be classified according to the set of “velocity classes” the functionally separate parts (i.e. clusters or sets of clusters that will only interact with others within the set) belong to. By a “velocity class” I just mean all the separate parts that are moving across the Life field in the same direction and with the same speed (still lifes and oscillators belong to the zero-velocity class).

For one and two cell patterns, the set of final velocity classes is of course empty for all patterns; this is symbolised thus: {}. For all three and four cell patterns, the set is either empty, or consists only of the zero-velocity class, which I’ll call either ZV, or (0|0)/n. In the latter, the first and second numbers within the parentheses give the distances respectively east and north (the choice of east and north as positive, and the east-then-north order, are arbitrary) the pattern moves over the course of a “translation cycle” – the interval between two appearances of the same pattern, possibly translated. (The “n” is a placeholder for an integer recording the number of steps the pattern takes to translate itself – the natural way of treating static patterns in this scheme is to let the number represent the period over which the pattern repeats itself: 1 for a still life, 2 for a blinker, etc. But I’ll discuss periodicty in a later post.) Thus a glider travelling north-east is in velocity class (1|1)/4, a *WSS going south in class (0|-2)4. When we’re only dealing with static debris, gliders and *WSSs, we can substitute the more readable compass headings, so a glider going north-east is in class NE:c/4 and a *WSS going south in class S:c/2. This simpler formalism can be used for other spacships travelling in the same set of directions, but does not encode the period) For five cells, in addition to these possibilities, the set may consist of {(1|1)/4} – the glider, or {(0|0)n, (1|1)/4}, (1|-1)/4, (-1|-1)/4} – the r-pentomino; or in the more readable formalism {NE/4} and {ZV, NE/4, SE/4, SW/4}. I’ll use this simpler formalism in this post, but the less readable but more comprehensive and informative version is now available if needed. In fact, it classifies patterns more finely than by velocity class as defined above, because patterns travelling in the same speed and direction take different numbers of steps to effect a translation.

To avoid ambiguity, I’ll always list the non-zero velocity classes so headings closest to north when turning clockwise from that orientation (so, north first, north-east before east, east before south-east). So, if gliders are escaping but there are no orthogonal spaceships, NE/4 will always appear, if gliders are going in two directions but there are no spaceships NE/4 and either SE/4 or SW/4 will appear; but if there is for example an escaping LWSS, N/2 will begin the list or immediately follow ZV, and even if there are gliders as well, NE/4 might not appear, as the gliders may all be travelling at an angle of 135 degrees to the LWSS. If I illustrate with a pattern, I will rotate andor reflect it if necessary to conform to this directional convention. As should be obvious, if n-cell patterns allow a given set of final velocity classes, so do all larger numbers of cells, if only by adding single cells too far away to make a difference (note that I’m allowing all patterns here, not excluding isolated cells or parts that never interact).

So with 1 cell (or 0 cells), we have:
{}

With 3 cells, add:
{ZV}

With five cells, add
{NE/4}
{ZV, NE/4, SE/4, SW/4}

With six cells, it turns out we can add:
{ZV, NE/4} (This is the block and glider.)
{ZV, NE/4, SE/4} (This is the Herschel, among others.)

With seven cells add:
{NE/4, SE/4}
{ZV, NE/4, SW/4}
{ZV, NE/4, SE/4, SW/4, NW/4}

All these are illustrated by examples in the rle shown below, where patterns starting with more cells are shown further down. Seven cells is as far as I have made a comprehensive check of all possibilities (doing so this far was a byproduct of the search for infinite growth patterns with up to 10 cells, going on to check all possibilities for eight or more cells would require significant additional work – I may come back to it). However, I have found an 8-cell pattern which exemplifies the set {NE/4, SW/4}, also shown. That leaves only two sets involving only static debris and gliders without an example: {NE/4, SE/4, SW/4} and {NE/4, SE/4, SW/4, NW/4} – gliders going in three or all four directions, with no static debris. The former can certainly be done with 12 cells: the 7-cell pattern {ZV, NE/4, SW/4} plus a glider; and the latter in 14, by combining two of that 7-cell patterns in different orientations. These are shown as well.

Code: Select all

x = 8007, y = 28005, rule = Life
o4000$o$o$o3998$3o3997b2o$2bo3999bo$bo4000bo$4002bo3997$o3999bo$o4000b
2o$ob2o3999b2o$bo4000bo3997$obo3997bobo3998bo2b3o$bo3999bo3998bo2bo$bo
4000bo3998bo$b2o4000b2o$o4004bo3996$3o$3bo$bo$2b3o3997$3o2bobo$o5bo$bo
4bo$6b2o$5bo3996$obo3bobo$bo5bo$bo5bo$2o5b2o$2bo3bo!
With eight cells or more, of course, additional velocity classes are possible, as *WSSs can be produced. I will deal with those in a separate post, as there are three different types of *WSS (LWSS, MWSS, HWSS) to consider, as well as more complex spaceships with the same velocity.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 10th, 2018, 12:34 pm

2718281828 says:
As an id for a methuselah I suggest the pattern with maximum population (until time to stability), in case of a tie - just breaking it e.g. by the first occurring maximum
I haven't looked much at intermediate cell-counts, but that's a perfectly sound measure. However, I think the problem with "methusaleh" is that it's just an ill-defined term. There are several ways it could be defined precisely, of which you suggest one, but no particular reason I can see for preferring one over another.

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Systematic survey of small patterns

Post by 2718281828 » December 10th, 2018, 6:26 pm

NickGotts wrote:2718281828 says:
As an id for a methuselah I suggest the pattern with maximum population (until time to stability), in case of a tie - just breaking it e.g. by the first occurring maximum
I haven't looked much at intermediate cell-counts, but that's a perfectly sound measure. However, I think the problem with "methusaleh" is that it's just an ill-defined term. There are several ways it could be defined precisely, of which you suggest one, but no particular reason I can see for preferring one over another.
Well, but I think this definition is not ill defined if the population of a pattern is bounded (and ignoring problems as http://www.conwaylife.com/wiki/Fermat_prime_calculator).
Then we can always detect the pattern with the population maximum in its evolution.
In case of a tie I suggested first to take the first maximum. But I think it is better to take the latest population maximum if the resulting pattern is not a collection of oscillators (incl. still lifes). If the population maximum is attained for a collection of oscillators then taking the first occurring maximum (but it does not really matter the pattern is periodic anyway). This automatically would solve the problem that occurs when a very far glider would hit a collection of oscillators, e.g. for the two pattern

Code: Select all

x = 47, y = 26, rule = B3/S23
24bo$22bobo$23b2o13$2bo$obo$b2o2$3b4o33b4o$2b6o31b6o$b8o29b8o$2o6b2o
27b2o6b2o$b8o29b8o$2b6o31b6o$3b4o33b4o!
the first one would classify it.
Of course, this classifies all pattern with bounded population, and clearly not all of them are regarded as methuselah. But if we take certain constraints on this set we get close (e.g. min time-to-stability, MCPS, certain increase (e.g. doubling) in population during life time, etc) to what we want.

In this post: viewtopic.php?f=2&t=1849&start=150#p66338 on natural mehuselah in 5x5 soups the definition seems to work fine (even though I used the first maximum as identifier).

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 12th, 2018, 2:59 pm

This post is about 8-cell patterns that produce *WSSs.

There are no patterns with fewer than eight cells that produce any form of spaceship other than a glider. With 8 cells, of course you can produce an LWSS (just remove the spark from the LWSS’s recurring 9-cell pattern). But it turns out both the MWSS and HWSS can emerge from an 8-cell starting pattern, although in all those cases there will also be static debris and gliders.

The rle code below is for a field containing examples of all the possible velocity-class sets involving *WSSs, when starting with 8 cells. In fact, these patterns, together with some minor variants as described below, and rotations and reflections, are all those 8-cell patterns which produce a *WSS. The gaps in the rows are where patterns that do not produce a *WSS, but were selected by the scripts I used, were removed. The scripts all looked, among some subset of 8-cell patterns, for those that did not, after 8192 steps, consist solely of a stationary pattern repeating on a cycle that is a factor of 12, plus retreating gliders that will not interact with anything in future. Some of those removed patterns are “methusalehs” that just take more than 8192 steps to stabilise (discussed in an earlier post). Others, to be discussed in a later post, do actually consist of a stationary pattern plus retreating gliders at 8192, but include a pentadecathlon – so their stationary portion is not the same after s+12 steps as it is after s steps.

Code: Select all

x = 2040028, y = 300076, rule = B3/S23
o39999bo40000bo39998b3o39997b3o39997b4o39996b4o40001bo39994bo40001bo
39999bo39997bo39999bo39999bo$o39999bo39999b3o39997bo40002bo39996bo3bo
39995bo39999bo40003bo39995b2obo39996b2obo40001bo39995bo5bo39993bo$obo
39997bobo39997bo2b2o39998b2o39998bo39996bo39999bo3bo39995bobob2o39994b
2ob2o39997bo40001bo39995b2obobo39996bo39999bo4bo$4bo40000bo39996bo
40002bo39998b2o39995bo39999bo40001bo40001bo39998b3o39994bo2bo39997bo
40000b4o39996b4o$2b3o39997b3o79999bo40001bo119995bo39999bo80003bo
39997bo59996$o3bo39995bo39999bo39999b3o2bo39994b3o2bo39994bo39999bo
39999bo39999bo39999bo2b3o39994bob2o39996bo2b3o39996bo39999bo39999bo
39999bo39999bo39999b2o39999bo39997bo3bo39995bo39999bo39999bo39999bo
39999bo$obo39997bobo39997bobo39997bo2bo39996bo2bo39997b2o2bo39994bobo
39997bobo39997bobo39997bo3bo39999bo39997bobo39995bobo39997bobo39997bob
o39997bobo39997bobo39997bo39999bobo39998bobo39996bobo39997bobo39997bob
o39997bobo39997bobo$o2bo40002bo79994bobo39999bo39996bo2bo159998b2o
39996bo2b3o39994bo2bo40002bo199995bo39999bo39997bo2bo160002bo$3bo
39998bobo39997bobobo79994bo39999bobo39998bob2o39996bobobo39995bobo
159997bobo39997bobobo39995bob2o39996bobobo39995bobo39997bo80001bo
39997bob2o39996bobobo39995bobo39997bobo39997bobobo$bo40003bo39999bo
160000bo39998bo39999b2o159998bo39999bo40000bo39998bo39999b2o39997b3o
39995bob3o39995bo40003bo39998bo39999b2o39998bo39999bo$40004bo39999bo
159998bo39999bo39999bo160000bo39999bo39998bo39999bo39999bo159999bo
39999bo39999bo40000bo39999bo59995$24b3o39983b3o39987b2o39998b2o80001b
2o79999b2o39994b3o39997b3o39997b2o40015bo39982b2o40006bo39993b2o39997b
o120008b2o39989bo$2o22bo2bo39982bo2bo39986bo39999bo80002bo80000bo
39995bo2bo39996bo2bo21b2o39973bo40015b2obo39980bo40006b2obo39991bo
39997b2obo120006bo39989b2obo$o360024bo39991bo39999bo79990bo79992bo
159999bo$400016b2obo39980b2o40006bo$400017bo39982bo40006b2obo39989b2o$
480008bo39991bo3$80003b3o199994b3o$40000b2o40001bo2bo199993bo2bo40007b
2o$40000bo280010bo399989bo$720000b2obo40006b2o$720001bo40008bo5$
120002b3o79995b3o$120002bo2bo79994bo2bo6$560001bo$560000b2obo39998b2o$
560001bo40000bo59974$3o39997b3o40007b3o39996b3o39988b3o40003b3o39991b
3o40001b3o39993b3o40005b3o39989b3o39997b3o40009b3o40001b3o39997b3o
39981bo40012bo39986b3o39997b3o39997b3o39997b3o39997b3o40004b3o40009b3o
40000b3o39975bo40004bo$80010bo2bo39995bo2bo79993bo2bo119990bo2bo79996b
o2bo39996bo2bo120012bo2bo39980bo40012bo39986bo2bo319996bo40004bo$
600000bo40012bo359986bo40004bo$560000bo120017bo39999bo$560000bo120017b
o39998b2obo$560000bo120017bo39999bo159982bo$880000b2obo$200000b3o
120003b3o480002bo79989bo$16b3o519981b3o280007b2obo159987bo$16bo2bo
519980bo2bo280007bo119989bo39998b2obo$160008b3o199989b3o559997b2obo
39997bo$160008bo2bo199988bo2bo400009bo159987bo$40012b3o439985b3o
280009b2obo239997bo$40012bo2bo439984bo2bo280009bo239998b2obo$600011b3o
39986b3o360010bo$600011bo2bo39985bo2bo200005bo$840008b2obo$240004b3o
39993b3o560006bo199991bo$240004bo2bo39992bo2bo759996b2obo$80000b3o
360007b3o599988bo3$120000b3o280006b3o59978$120012bo39987b2o39998b2o
39998b2o39998b2o120008b2o39988bo80020b2o120005b2o40001b2o39999b2o
40011b2o$120012b3o39985bo39999bo39999bo39999bo120009bo39989b3o80018bo
120006bo40002bo40000bo40012bo$120000b2o11bo319987bo$120000bo8$440011b
2o$440011bo279988bo$720000b3o$720001bo14$160011bo79998bo$160011b3o
79996b3o$160012bo79998bo2$520000bo$520000b3o$520001bo5$400000bo$
400000b3o$400001bo$200010bo439989bo$200010b3o439987b3o$200011bo439989b
o4$760000bo$760000b3o$760001bo2$280009bo$280009b3o$280010bo7$680000bo$
680000b3o$680001bo59937$80000b3o79997b3o39997b3o39997b3o40006bo39990b
3o39997b3o39998b3o79996bo39999bo80011b3o39985bo40018b3o40005b3o40000b
3o39999b3o80001b3o39998b3o40002b3o39955bo80051b3o39983bo39993bo39967bo
40011bo39987bo39999bo40008bo39990bo40004bo39994bo79999bo40003bo79995bo
119999bo40018bo80001bo39999bo80005bo$280009b3o199988b3o39997b3o119997b
3o359997b3o120035b3o39991b3o39965bo40011b3o39985bo39999bo40008b3o
39988bo40004b3o39992bo79999b3o40001bo79995b3o119997b3o40016bo80001bo
39999bo80005bo$200010bo79999bo199990bo39999bo119999bo359999bo120037bo
39993bo39966bo40012bo39986bo39999bo40009bo39989bo40005bo39993bo80000bo
40002bo79996bo119999bo40017bo80001bo39999bo80005bo$200010b3o$200011bo
319997b3o1280004bo$1000042b3o799971bo$1560002bo240013bo$1560002bo$
1560002bo$400000bo$400000b3o$400001bo$1680008bo$1680008bo$1680008bo2$
800000bo1239999bo$800000b3o79997bo39999bo1119999b3o$800001bo79998b3o
39997b3o1119998bo$880001bo39999bo$80028bo$80028b3o1279969bo$80029bo
1279970bo$1360000bo2$1240000bo$240009bo79994bo919995bo$160011bo79997b
3o79992b3o919993bo$160011b3o79996bo79994bo1000004bo$160012bo439987bo
680009bo39999b3o$600000b3o600010bo79996b3o39998bo$600001bo600011b3o
79995bo$1200014bo239985bo$480008b3o160007b3o319979bo440004bo39994bo$
960000b3o440002b3o39992bo$280000b3o679998bo440004bo199993bo$1600000b3o
$1600001bo4$680000bo$680000b3o$680001bo399998bo400002bo$760000bo
319999b3o400000b3o$760000b3o319998bo79998bo320003bo$760001bo399998bo$
1160000bo679999bo$1840000b3o$1840001bo119998bo$1960000b3o$360002bo
759997bo840000bo$360002b3o759995bo$360003bo759996bo9$720000bo$720000b
3o$720001bo9$1920000bo$1920000b3o$1920001bo!
The top row (row 1) consists of 14 single-cluster patterns that increase their cell-count on the first step. The full set of these (not counting rotations and reflections) was tested. The row includes six patterns that develop quickly into a single LWSS (velocity-class set {N/2} once rotated), seven that leave static debris and send out gliders in all four directions plus an LWSS (so their velocity-class set is {ZV, N/2, NE/4, SE/4, SW/4, NW/4}, of which five develop into the same stable state (columns 1, 2, 4, 8, 12). Column 3’s pattern produces gliders in three directions along with an LWSS, if rotated so the LWSS goes north its velocity-class set would be {ZV, N/2, NE/4, SE/4, SW/4}. There are two different ways a set of 3 glider-directions can relate to the direction of a *WSS: either the missing direction can be 45° away from the *WSS direction of travel, as in the current case, or 135° away from it (which would be symbolised {ZV, N/2, NE/4/, SE/4, NW/4}).

Row 2 consists of 25 single-cluster patterns that maintain the same cell-count (8) at step 1. Since all patterns up to 7 cells have been tested and none produce a *WSS, an 8-cell patterns that does so cannot have a cell-count below 8 at any stage: it may go through a number of 8-cell steps, but must eventually develop through one of the patterns that increases cell-count at step 1. Hence if there had been no *WSS producers among the latter, there would have been no need to test those having 8-cell immediate successors. As it is, we know there will not be any patterns that end up looking different from all those in row 1.

Row 3 contains 16 patterns that start as a 5-cell pi-predecessor and a preblock. There are two distinct 5-cell pre-pi patterns, not counting rotations and reflections; one of the two has reflectional symmetry on one orthogonal axis, which makes a difference if we want to start counting patterns, and comparing the numbers leading to paraticular results – see below. Row 3 includes examples of patterns producing a *WSS and gliders in two directions. There are four ways a pair of glider directions of travel can relate to a *WSS travel direction: the two glider directions may be opposite each other, or at a right angle; and in the latter case, the *WSS direction may be between the two glider directions (at a 45° angle with both), at a 135° angle with both, or at a 45° angle with one and a 135° angle with the other – the case here, symbolised {ZV, N/2, NE/4, SE/4}.

Each of the patterns in row 3 actually represents more than one distinct pattern, because the preblock can have any of four orientations. The sixteen patterns constitute four groups of four giving the same final pattern (modulo rotations/reflections), all producing a single LWSS. However, the first eight of the 16 patterns each represent four distinct possibilities (four different orientations of the preblock), while the other eight, in which the pi-predecessor has an axis of symmetry, each represent just two possibilities (or to put it another way, pairs of sets of 4 form mirror images). So in total, the patterns shown represent (8*4)+(8*2) = 48 distinct LWSS-producers.

Row 4 is of 27 patterns including a pi-predecessor and a blinker. It consist of three sets of nine patterns that give the same final nine results (three sets because one of the two pi-predecessors has an axis of symmetry which it shares with the blinker); all 27 produce a single LWSS plus debris. New velocity-class sets in this row are {ZV, N/2, NE/4, SE/4, NW/4} – first appearing in column 1, once reflected left-right; {ZV, N/2, SE/4} (appearing first in column 3, after rotation), and {ZV, N/2} (appearing first in column 7).

Row 5 is of 12 patterns consisting of an r-pentomino and pre-block. The pattern in column 6 (the third pattern in the row as columns 1-3 are empty) produces an HWSS, the other 11 an LWSS each. No new velocity-class sets appear. Each pattern in this row represents no fewer than 36 distinct staerting patterns, since any orientation of the preblock can be combined with any of nine 5-cell patterns: the r-pentomino itself (as shown), its six 5-cell parents and two 5-cell grandparents.

Finally, row 6 is of 39 patterns each consisting of an r-pentomino and blinker. In each case, any of the r-pentomino’s eight 5-cell predecessors could be substituted for it, so each pattern shown represents a set of nine.
• Patterns in columns 3, 5, 6, 7, 8, 10, 11, 13, 14, 18, 19, 20, 21, 25, 26, 28, 29, 30, 33, 34, 35, 36, 38, 41, 43, 46, 47, 49 and 52 produce an LWSS. So 29*9=261 in all.
• Those in columns 9, 16, 17, 23, 24, 31, 37 and 50 produce an MWSS, so 8*9=72 in all. Column 17 yields a new velocity-class set: {ZV, N/2, SE/4, SW/4}.
• Number 40 produces an HWSS. Note that the r-pentomino and blinker are quite close, but it has been checked that all the 5-cell r-pentomino predecessors could be paired with a blinker to produce the pattern. So 9 in all. The velocity-class set is novel: {ZV, N/2, NE/4, SW/4}.
• Number 32 produces two LWSSs travelling in opposite directions. Again, representing 9 patterns. The velocity-class set for the pattern is {ZV, N/2, NE/4, SE/4, S/2, SW/4, NW/4}.

Summing up, if my search strategy, Python script coding and arithmetic are correct, there are 771 distinct 8-cell patterns that produce a single LWSS, or 771*8 = 6168 counting rotations and reflections (none of the patterns have any symmetry when considered as a whole), and 9 (72 with rotations and reflections) that produce two LWSSs. There are 73 that produce an MWSS (584 with rotations and reflections), and 45 that produce an HWSS (360 with rotations and reflections). In Sparse Life (see above), *WSSs of all three types (LWSS, MWSS, HWSS) produced from 8-cell starting patterns will hugely outnumber all others of the same type, once the initial few thousand steps are complete. The LWSS, MWSS and HWSS population ratios to be expected in a sufficiently large chunk of the field are 789::73::45.

Finally for this post, two copies of the two-LWSS producing pattern, arranged at right angles, can readily make a 16-cell pattern that sends spaceships in all either cardinal and semi-cardinal directions (and leaves static debris) – velocity-class set {ZV, N/2, NE/4, E/2, SE/4, S/2, SW/4, W/2, NW/4}. But we can do at least a little better: since a glider can hit a beehive in a way that results in an r-pentomino (or rather, the r-pentomino’s fifth successor), and the beehive has 4-cell predecessors, a blinker and an accompanying straight row of 4 (which becomes a beehive) can be placed so a glider from one copy of the two-LWSS pattern hits the blinker, and the combination develops as a second copy of the two-LWSS pattern, at right angles to the first. An example pattern is shown below:

Code: Select all

x = 181, y = 312, rule = B3/S23
178bo$178b3o$179bo23$166bo$166bo$166bo273$25bo$25bo$25bo6$o$o$o$o!
Last edited by NickGotts on December 12th, 2018, 3:28 pm, edited 1 time in total.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 12th, 2018, 3:05 pm

2718281828,

I have to admit I don't quite understand your definition of a "methusaleh" - I'm not sure I could apply it to decide whether a given pattern is a "methusaleh", or which of two "methusalehs" is more methusalehish. Usually, they are described in terms of the number of steps to stability rather than maximum size. But in any case, I see no point in arguing about definitions of a class I've never found very interesting!

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » December 12th, 2018, 5:51 pm

This post is about oscillators, and particularly, oscillator periods.

For patterns up to six cells, the only oscillators that appear in the final static debris (I have not checked all intermediate steps) have period 2 (add period 1 if you want to regard still-lifes as period 1 oscillators!). Up to five cells, only the blinker appears. Six cells give us the toad, beacon and clock, which of course all appear as starting patterns. But all these are period 2.

The first oscillator of any other period (unless we want to count gliders as “moving oscillators” of period 4) appears as the end result of 7-cell starting patterns: the pulsar. The pattern below shows the 18 distinct 7-cell pulsar-predecessors: six which immediately increase cell-count on step 1 in the upper row, 12 that do not in the lower. None produce anything in addition to a pulsar.

Code: Select all

x = 227, y = 43, rule = Life
o3bo16bo19bo19bo18b5o15bo5bo$obobo20bo18b2o18bo15bo3bo16b2ob2o$o3bo15b
ob3o15bob2o16bob2obo37bo2$21bo20bo19bo36$2o2b2o14b2o2bobo13b2o2bo15bob
ob2o14bobobobo13bobobo15bobo2bo15b2ob2o15b2obo16b2o2bo15bo2bo17bobo$2b
o3bo15bo2bo16bo2b2o14bo4bo14bo3bo15bo3b2o14bo2bobo13bo5bo13bo4b2o13bo
3bobo13bobo2b2o13b2o3b2o$3bo19bo19bo19bo19bo19bo19bo19bo19bo19bo19bo
19bo!
Five of the 18 have an orthogonal axis of reflection symmetry, and one has two such axes. This means that counting rotations and reflections, there are (8*12)+(5*4)+(1*2) = 118 such patterns.

Turning to 8-cell starting patterns, there are considerably more pulsars, some appearing along with other debris and gliders, but also, the first pentadecathlons appear. There are three 8-cell patterns that produce a pentadecathlon alone, and 12, all closely related, that produce one plus other debris and gliders. The three are in the upper row of the pattern below (as can be seen, they are three successive steps in the same pattern development), the three in the lower row quickly become identical to each other; each represents four possibilities, as the pre-block can take any orientation:

Code: Select all

x = 4, y = 10, rule = Life
2bo2$b3o5$b3o2$2bo!
Note, 12th June 2019: the above rle is wrong. The one I should have posted is:

Code: Select all

x = 65, y = 39, rule = Life
22bo$31bobo8bo$21b3o8bo8b3o$32bo3$32bo$21b3o8bo8b3o$31bobo8bo$22bo21$
2b3o27b3o28bo$bo2bo27bo2bo26b3o2$63bo3$2o28b2o$o29bo29b2o$60bo!
There are therefore 15 distinct 8-cell patterns that produce pentadecathlons, and, because the top-row patterns have two axes of symmetry, (3*2)+(12*8) = 102 counting rotations and reflections.

There are no patterns with 8 or fewer cells that produce oscillators with periods other than 2, 3 and 15 – and no oscillators with period 3 other than pulsars, or period 15, other than pentadecathlons.
Last edited by NickGotts on June 12th, 2019, 5:48 am, edited 1 time in total.

User avatar
2718281828
Posts: 738
Joined: August 8th, 2017, 5:38 pm

Re: Systematic survey of small patterns

Post by 2718281828 » December 12th, 2018, 6:54 pm

NickGotts wrote:2718281828,

I have to admit I don't quite understand your definition of a "methusaleh" - I'm not sure I could apply it to decide whether a given pattern is a "methusaleh", or which of two "methusalehs" is more methusalehish. Usually, they are described in terms of the number of steps to stability rather than maximum size. But in any case, I see no point in arguing about definitions of a class I've never found very interesting!
I do not want to 'define'a methuselah but just a class of pattern that includes these pattern that are commonly referred as methuselah (e.g. pi and R). The type of questions I would like to answer are:
How many single cluster pattern of 7 cells evolve to the pi:

Code: Select all

x = 22, y = 4, rule = LifeHistory
20.A$3A16.A.A$A.A16.A.A$A.A16.A.A!
And by pi I mean not just the left pattern (which is visually the pi) but also the right one as it evolves into the same pattern sequence. And just to classify if a pattern is counted as pi or not I suggest the identifying pattern of the population maximum. But the same principle might be applied to other pattern as well, e.g. spaceships, oscillators, honey farm predecessor, etc.

It also helps for non-cluster pattern. You mentioned pattern like pi/R+preblock/blinker pattern in different 'styles' (not rotation/orientation) so having 4 different preblocks and different R/pi predecessors.
If you take e.g. these 8 pattern:

Code: Select all

x = 263, y = 91, rule = B3/S23
14$78b3o$22b3o52bo2bo$21bo2bo3$245b3o$76bo90b3o75bo2bo$20b2o54b2o89bo
2bo$20bo3$244bo$165b2o76b2o$165bo47$23b3o$22bo2bo140b3o$166bo2bo$252b
3o$85b3o164bo2bo$84bo2bo$21b2o$22bo141bo$164b2o$250b2o$84bo166bo$83b2o
!
given my definition they would be classified as the same pattern (say methuselah), because they share the same maximum population pattern:

Code: Select all

x = 909, y = 776, rule = B3/S23
54b2o$54bobo$54bo271$427b2o$427b2o6$460bo$459bo2bo$459bo2bo6bo$446bo
14bo6bobo$445bobo20bobo$446bo22bo5$428bo$427bobo21b2o10b2o$427bobo20bo
2bo9b2o$428bo12bo8bobo$440bobo8bo$423b2o7b2o5bo2bo$422bo2bo5bo2bo5b2o$
423b2o7b2o$451bo$428bo21bobo$427bobo19bo2bo$406bo20bobo20b2o$405bobo
20bo35b2o$406b2o55bobo$410b2o52bo$409bobo39b2o49b2o$410bo40b2o49bobo$
503b2o$462bo$426b2o34bo$394bo31b2o34bo$393bobo49b2o37b2o$394b2o49b2o
17b2o18b2o$464b2o$439bo$439bo52b2o$439bo52b2o2$434bo$434bo16b2o$434bo
16b2o$403bo$402b2o$401bo$403b5o$400b5o2bo$401bo41bo$405b2o35bobo$425b
2o14bo3bo$404b3o17bobo14bo4b3o$403b2o2bo17bo15b2ob2o2bo$404bo2bo21b2o
4bob2obo3bob2o$405b2o21bo2bo4b6o$428bob2o7bo3bo$428b2o2b2ob2o9b2o$427b
2ob4ob2ob2obo6bo$404bo21bob4obo4bo2bo5bo$403bobo19b3obo2bo4b9o$402bo
23bobo3bo4bo4bo2bo$406bo20b2o3bo5b2o4bo5bo$394b3o9bo12b2o12bo8bo2bo4b
2o$394bo3bo3bobobo3b3o6b2o21b4o6bo5b3o$394b4o5bo13b3o21b2o4b2o9bo3bo
21b2o$412bo4b3o22bob6o8bo4bo20b2o3b2o$404bo2bo6bobo3bo25b2o7bo3b2o2bo
25b2o$404bo9bob2o2bo28b2o4bo3bo3bo$414b3o9b2o29b3ob2o$407b5o4b4o8bo26b
obo$420bo4bo2bo26bob3o8b3o$410bo6bob2o6bo$408bob2o5bo2b2o3b2o12b2o$
401b3o3bo2bo6bobo2bo15bo2bo$400bo2b3o2b3o10bobo15bobo$404b2obobo11bo2b
o3bo11bo51bo$400b3o2bo2bo7b3ob6o3bo2b2o57bobo$402b2ob2ob2obo4b2o3bob2o
6bo2bo56b2o$403bobo3bobo8bo6b2o2b3o$402b3o9b2o5b3o8b2o17bo$402b2obo7b
3o8b2o25bo$403b4o4b3obo35bo$402bo3bo4b2o9b2obo63b2o$402bob2o5b2o2b3o5b
2ob2o7b2o52b2o$402bobo10b2o6b2obo7bobo$403bo8bo2b2o3bo4bo9bo49b3o$413b
3o3b2o$414bo3b2obo61bo5bo$419bobo61bo5bo$420b2o4bo56bo5bo2$485b3o2$
483bo$406b2o17b2o55bobo10b2o$406b2o17b2o55bobo10b2o$483bo2$405b2o$405b
2o2$466b2o$422b2o42bobo$421bo2bo42bo$422b2o$442b3o28b3o2$419b2o37b2o$
419b2o37b2o2$449b2o19b2o$449b2o19b2o$435b3o$440bo$439bobo$439bobo$401b
o15b2o21bo$401bo15b2o$401bo42b2o$443bo2bo$444b2o5$423b2o$423b2o6$424b
3o5$410b2o$410b2o$428b2o$428b2o$421b2o$421b2o119$279bo$277b2o$278b2o
207$907bo$908bo$906b3o23$2bo$2o$b2o!
in the evolution.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Systematic survey of small patterns

Post by 77topaz » December 18th, 2018, 3:11 am

A minor note: the correct spelling is "methuselah", not "methusaleh".

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » January 2nd, 2019, 1:54 pm

Thanks for that correction, 77topaz.

Progress report: I've now surveyed all the three-cluster 9-cell patterns (the 3-3-3s), and those two-cluster (6-3 and 5-4) patterns in which the larger initial cluster does not, when run by itself turn into a glider, or produce any gliders. Nothing of particular interest found (more pentadecathlons, more methuselahs but none approaching the 9-cell record holder, Bunnies 9: http://www.conwaylife.com/wiki/Bunnies_9).

That just leaves the 6-3 and 5-4 patterns in which the larger initial cluster either turns into a glider, or produces at least one glider (plus static debris). These are of course the trickiest, since one must account for cases where a glider hits the smaller cluster - before or after it has stabilised - and the resulting reaction interacts with other parts of the pattern produced by the larger cluster, including those where it produces further gliders that hit that pattern, with the possibility of yet more gliders... I've done quite a bit of preliminary work, but completing the 9-cell survey will still take some time.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Systematic survey of small patterns

Post by NickGotts » April 10th, 2019, 5:31 pm

I believe I have now tested all the 9-cell patterns necessary to confirm that there are no infinite-growth patterns with less than 10 cells, reaffirming Paul Callahan's result of 1997. I will now continue on two lines of work in parallel:

(1) Checking through all my reasoning and code and possibly simplifying parts of it to produce something that could reasonably be called a proof - although I'm aware it will inevitably be short of mathematical standards of rigor, since parts of it will say, more or less, "run these patterns if you want to check that I'm right". I'll make this quasi-proof (assuming I don't find any errors, or gaps I can't patch) publicly available.
(2) Starting on the 10-cell patterns, specifically the single-cluster ones, for which the code is already prepared. I reckon there are around 90,000,000 of them, so this will take a while.

By the time I'm through with (2), I hope to have completed the checks of (1), and will then turn to the two- and three-cluster 10-cell patterns. My aim with the 10-cell patterns is to find all the infinite-growth starting patterns, and in particular to determine whether there are any that develop into anything other than block-laying and glider-stream switch-engines. (I don't believe there are likely to be - if there are, the most likely possibilities are two switch-engines, either separate from each other, or with one crawling up the side of the other and interacting with it.)

Post Reply