## Enumerating Still Lifes (in C)

For scripts to aid with computation or simulation in cellular automata.

### Re: Enumerating Still Lifes (in C)

chris_c wrote:My python script was too slow so I wrote something in C instead:

Thanks! I added a counter to verify that all patterns get tested, and I've tested that it reacts with Fail on a pattern such as:

`x = 12, y = 10, rule = LifeHistory9.2A\$2.2A.2A.A2.A\$2.2A.A3.2A\$5.A\$2.3A\$2.A\$2A\$A\$2.A\$.2A!`

Apple Bottom wrote:Simeks, does your program's design allow for dividing up the task of enumerating still lives of a given population?

Yes, good idea, it should be pretty straight-forward to do this!

EDIT:
I wrote:The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3.

I was able to improve speed by a factor of 3.6, and on a slighly faster computer, with a 4.4 GHz Haswell core, the running time for the 24 bit still lifes is down to 52 minutes.

EDIT 2:
Result for 26 bit still lifes:
Strict still lifes: 24619307
Pseudo still lifes: 20463274

EDIT 3:
A note on the implementation of my still life searcher:

Reading Mark Niemiec's description of his search program in the Deficiencies section, it appears subtle bugs were starting to show up around 24 or 25 bits in his implementation. Appearently this is caused by restricting placement of new on-cells at a (2,0) or (2,1) distance from the closest previous on-cell to a few carefully selected special cases.

In my program I don't grow patterns from a corner, but instead from this start, where the white cell must be on and the red cells are open to define:

`x = 20, y = 40, rule = LifeHistoryD.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$D.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$C16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D!`

Any (finite, non-empty) pattern, if rotating/mirroring is not allowed, can be placed in exactly one way in that area, which should guarantee that any subpattern will be generated exactly once, for example like this:

`x = 244, y = 40, rule = LifeHistoryD.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D\$D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D12.16D.D.D\$17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D13.17D.D\$16D.D.D12.2D2C12D.D.D12.16D.D.D12.3DC12D.D.D12.2D2C12D.D.D12.16D.D.D12.2D2C12D.D.D12.16D.D.D\$17D.D13.3DC13D.D13.17D.D13.D3C13D.D13.2DC14D.D13.17D.D13.2DC14D.D13.17D.D\$16D.D.D12.3C13D.D.D12.2C14D.D.D12.C15D.D.D12.CDC13D.D.D12.C15D.D.D12.CDC13D.D.D12.2C14D.D.D\$2C15D.D13.C16D.D13.CDC14D.D13.2C15D.D13.2C15D.D13.3C14D.D13.2C15D.D13.C16D.D\$.C14D.D.D13.15D.D.D13.DC13D.D.D13.15D.D.D13.15D.D.D13.2DC12D.D.D13.15D.D.D13.3C12D.D.D\$.CDC13D.D14.16D.D14.D2C13D.D14.16D.D14.16D.D14.D2C13D.D14.16D.D14.2DC13D.D\$.D2C12D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D14.16D.D\$.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D13.15D.D.D\$2.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D\$2.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D15.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D13.D.D.D.D.D.D.D.D.D.D!`

As far as I can think of I don't make any dangerous assumptions about where new on-cells can be placed. For example the program will happily build and continue to search from an intermediate pattern like this:

`x = 20, y = 40, rule = LifeHistoryD.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$D.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$D4.12D.D\$5.11D.D.D\$2.2C.12D.D\$3.C.11D.D.D\$3C2.12D.D\$C4.11D.D.D\$4.13D.D\$C4.11D.D.D\$3C2.12D.D\$3.C.11D.D.D\$2.2C.12D.D\$5.11D.D.D\$5.12D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D!`

because it could possibly be completed to a still life for example like this:

`x = 20, y = 40, rule = LifeHistoryD.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$D.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$17D.D\$16D.D.D\$D7.9D.D\$9.7D.D.D\$2.2C.2C3.7D.D\$3.C.C5.5D.D.D\$3C3.3C3.5D.D\$C7.C4.3D.D.D\$8.C.C2.4D.D\$C5.2C.2C2.3D.D.D\$3C4.C5.4D.D\$3.C.C.C4.4D.D.D\$2.2C.2C3.7D.D\$9.7D.D.D\$8.9D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$.16D.D\$.15D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D\$2.D.D.D.D.D.D.D.D.D\$.D.D.D.D.D.D.D.D.D.D!`

Instead it seems I am able to reach about the same asymptotic speed of O(2.6^n) as Mark Niemiec by a careful selection of the search order.

EDIT 4:
Result for 27 bit still lifes:
Strict still lifes: 60823008
Pseudo still lifes: 52816265
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

I've posted a test release of the still life searcher here

Note: I've also edited my previous post multiple times.

Should work well on Windows and Linux. Try the Windows version if you can, it has a nice visualization window!

Windows executables are included, run from a DOS window. Use sc256 if you have a Haswell or later CPU or sc128 if not.

For Linux, compile with "mknative".

Usage is:

> sc128 <command> <min on cells> <max on cells> [<selected subset>]
where <command> is "w" to write database files, or "c" to only count still lifes.

Pick a suitable <max on cells>. You can generate databases for lower bit counts in the same run in virtually no extra time, for example:

> sc128 w 4 22

will generate 38 different files in the current directory, one for each bit count, and one each for strict and pseudo still lifes.

The program will keep an eye open for any triple or quad pseudo still life, and report them to stdout (the console) if any are found. The smallest known of these types has 32 on-cells, but there could possibly be smaller ones.

To redirect stdout to a file, use for example:

> sc128 w 4 22 >out.txt

On the suggestion of Apple Bottom, I've implemented the possibility to search a subset of the search space.

There is currently a fixed set of 100 subsets that require about an equal amount of time to complete. They are numbered from 0 to 99, for example:

> sc128 w 31 32 91 >out.txt

will generate database files such as "32_bits_strict_subset_0091_of_0100.txt". The running time for searching one subset to 32 bits should be around a day. You can of course start one search for each CPU core of your computer in different subsets at the same time.

Note that it is normal for subset number 2 to contain no strict still lifes, only pseudo still lifes, so the corresponding database file will be empty.

If someone wants to set up a community search up to a larger bit count than 32 bits, I can post a version with a higher number of subsets.
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:I've posted a test release of the still life searcher here.

Wonderful! I just gave it a test -- using one HT core on a Core i7-3770K (supporting AVX but not AVX2), it took roundabout 15 minutes to compute everything up to 22 bits. That's quite impressive. And I like the visualization window, that's a nice touch.

Output's a bit jumbled, for some reason:

`\$ time ./sc128.exe w 4 22 |tee 4-22.txtCells open to define and the (4, 64) cell that should always be on:x = 64, y = 128, rule = LifeHistory4\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.subset = -1, min = 4Not stable = 721221908, not canonical = 14977582, not connected = 193287Number of on-cells:          4Result for full search space:Strict still lifes:          2Pseudo still lifes:          0Number of on-cells:  56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.56D\$4.A55D\$5.55D\$5.55D\$5.55D\$5.        5Result for full search space:Strict still lifes:          1Pseudo still lifes:          0Number of on-cells:          6Result for full search space:Strict still lifes:          5Pseudo still lifes:          0Number of55D on-cells:          7Result for full search space:Strict still lifes:          4Pseudo still lifes:          0Number of on-cells:          8Result for full search space:Strict still lifes:          9Pseudo still lifes:          1\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.5Number of on-cells:          9Result for full search space:Strict still lifes:         10Pseudo still lifes:          1Number of on-cells:         10Result for full search space:Strict still lifes:         25Pseudo still lifes:  5D\$5        7Number of on-cells:    .55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D\$5.55D!0 strict and 0 pseudo 22 bit still lifes so far8803 strict and 55225 pseudo 22 bit still lifes so far26293 strict and 71539 pseudo 22 bit still lifes so far58462 strict and 84332 pseudo 22 bit still lifes so far83739 strict and 95972 pseudo 22 bit still lifes so far99646 strict and 104337 pseudo 22 bit still lifes so far141339 strict and 128106 pseudo 22 bit still lifes so far178444 strict and 147869 pseudo 22 bit still lifes so far205486 strict and 162157 pseudo 22 bit still lifes so far228242 strict and 189946 pseudo 22 bit still lifes so far258997 strict and 203380 pseudo 22 bit still lifes so far284963 strict and 219239 pseudo 22 bit still lifes so far314910 strict and 230573 pseudo 22 bit still lifes so far359333 strict and 256623 pseudo 22 bit still lifes so far391732 strict and 277920 pseudo 22 bit still lifes so far403313 strict and 283035 pseudo 22 bit still lifes so far433782 strict and 306333 pseudo 22 bit still lifes so far456357 strict and 323082 pseudo 22 bit still lifes so far472798 strict and 332153 pseudo 22 bit still lifes so far497364 strict and 340995 pseudo 22 bit still lifes so far526043 strict and 353865 pseudo 22 bit still lifes so far559205 strict and 371219 pseudo 22 bit still lifes so far576999 strict and 392941 pseudo 22 bit still lifes so far591081 strict and 421296 pseudo 22 bit still lifes so far615536 strict and 434655 pseudo 22 bit still lifes so far636781 strict and 442280 pseudo 22 bit still lifes so far657355 strict and 450477 pseudo 22 bit still lifes so farPerformence timer report:Timer ticks/s: 3435937Elapsed time:  933495.279 ms     11Result for full search space:Strict still lifes:         46Pseudo still lifes:         16Number of on-cells:         12Result for full search space:Strict still lifes:        121Pseudo still lifes:         55Number of on-cells:         13Result for full search space:Strict still lifes:        240Pseudo still lifes:        110Number of on-cells:         14Result for full search space:Strict still lifes:        619Pseudo still lifes:        279Number of on-cells:         15Result for full search space:Strict still lifes:       1353Pseudo still lifes:        620Number of on-cells:         16Result for full search space:Strict still lifes:       3286Pseudo still lifes:       1645Number of on-cells:         17Result for full search space:Strict still lifes:       7773Pseudo still lifes:       4067Number of on-cells:         18Result for full search space:Strict still lifes:      19044Pseudo still lifes:      10843Number of on-cells:         19Result for full search space:Strict still lifes:      45759Pseudo still lifes:      27250Number of on-cells:         20Result for full search space:Strict still lifes:     112243Pseudo still lifes:      70637Number of on-cells:         21Result for full search space:Strict still lifes:     273188Pseudo still lifes:     179011Number of on-cells:         22Result for full search space:Strict still lifes:     672172Pseudo still lifes:     462086real    15m33.527suser    0m0.000ssys     0m0.046s\$ `

On the suggestion of Apple Bottom, I've implemented the possibility to search a subset of the search space.

That's very good as well! I see you've already computed the databases up to 27 bits -- I presume you're working on 28? Shall we divide up the work for the 29-bitters?

I'd propose that to do that we simply grab the next available subset(s), post a note in this thread saying what we've taken (to avoid duplicate work), and then start the computation. Post the results in this thread when the computation's done, and once the 29-bitters are done, we can move on to the 30-bitters, and so on.

I'll start by doing subset 0 of the 29-bitters!
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

Apple Bottom wrote:That's quite impressive. And I like the visualization window, that's a nice touch.

Thanks! I actually wrote the visualization for debugging of another project I'm working on, so I just threw it in...

Apple Bottom wrote:Output's a bit jumbled, for some reason:

I looks like output to stderr and output to stdout has somehow been intermixed. What if you only redirect stdout to a file (>out.txt) and let stderr go to the console?

Apple Bottom wrote:That's very good as well! I see you've already computed the databases up to 27 bits -- I presume you're working on 28? Shall we divide up the work for the 29-bitters?

Actually i started up an Amazon Ec2 server to generate the database for 25 to 30 bits. This was with an earlier version that had 16 subsets instead of 100. I'm running subset 0-3 of those 16 in parallel and they will complete soon. Luckily they correspond exactly to subset 0-24 of the new division.

I'm also running a count of the full 28 bits search that will complete soon, but without the database.
Would you like to start at subset 25 for bit count 25 to 30? Each one should take a bit over 5 hours at the speed you quoted.

In that case I'll continue at subset 50 when the current searches are done.
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:I looks like output to stderr and output to stdout has somehow been intermixed. What if you only redirect stdout to a file (>out.txt) and let stderr go to the console?

tee(1) should only touch stdout, but sure, I'll try that and see if it makes any difference.

Apple Bottom wrote:Actually i started up an Amazon Ec2 server to generate the database for 25 to 30 bits. This was with an earlier version that had 16 subsets instead of 100. I'm running subset 0-3 of those 16 in parallel and they will complete soon. Luckily they correspond exactly to subset 0-24 of the new division.

I'm also running a count of the full 28 bits search that will complete soon, but without the database.
Would you like to start at subset 25 for bit count 25 to 30? Each one should take a bit over 5 hours at the speed you quoted.

In that case I'll continue at subset 50 when the current searches are done.

Sure, that works! Bit count 25 to 30, subset 25; I'll also run subset 26 right afterwards (otherwise the core this is running on will be partially idle overnight).
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

New result:

Number of on-cells: 28
Strict still lifes: 150613157
Pseudo still lifes: 136655095
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:So far I have confirmed the numbers reported by Mark Niemiec for bit counts from 4 to 23. However for 24 bits my program finds 6 more scrict still lifes and 1 more pseudo still life than previously reported. My numbers are 4051732 and 3069135 respectively.

I'm fairly confident of the counts up to 23 bits, but not so much about the 24 bit ones. My algorithm has known defects (i.e. there are certain classes of objects it won't find), and I had to add those manually. The lists of extra objects is very small at 23 bits, but larger at 24, and would be over a hundred at 25 (which is one reason I had never attempted those). A couple of years ago, I made a change to the algorithm to explicitly look for the specific class of objects that were missed, and it did indeed find them (and no others), but that change caused it to lose one pseudo-object that had been previously found (a pond surrounded by four blocks). This means there is still some subtle bug in the algorithm, and I wouldn't feel comfortable running any larger searches until I figure out why that is happening.
simeks wrote:There is no database of 24 bit still lifes from Mark Niemiec's search, or anyone who has access to the code used for it? It would be interesting to find out if the extra still lifes I've found have any special propertly...

Definitely! Do you have any way of uploading your results in any format? Years ago, I had a similar discrepancy with H. Koenig on his searches, and by comparing the lists, I was able to find out which objects I found that he didn't, and also a few extra ones that he found that I didn't - which all turned out to be pseudo-objects that were erroneously classified as objects.
simeks"Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?[/quote]
I have a tool that takes a pattern list, and splits it into four separate output buckets - objects, pseudo-objects, quasi-objects (i.e. two adjacent tubs), and non-objects (e.g. constellations). I use this to post-process my own searches, as those output objects and pseudo-objects together. Ideally, the last two categories are always empty, unless something is seriously wrong.
[quote="simeks wrote:
I'm currently running the search for 25 bit still lifes, I will report the result soon. EDIT: The result I get is 9971377 strict still lifes and 7906676 pseudo still lifes.

Nice! As a sanity check, the number of 25-bit still-lifes are 2.46 times the number of 24s, which is exactly the ratio I would expect.
simeks wrote:The database will be two textfiles of this format: ...

This looks like RLE without the header, which should be very easy to parse and/or convert.
simeks wrote:The running time for 24 bits is about 4 hours, but I can see a simple way to improve speed by a factor of 2 or 3. The asymptotic speed is around O(2.6^n), the same as reported by Mark Niemiec.

This is much better than mine. The last recorded times I had for my earlier runs were 47 hours for the 21-bit ones, which would be 32 days for the 24-bit ones. I think my last runs were faster, but not nearly that fast.
simeks wrote:I'm sure the program can be adapted for other rules, but there are some assumptions about the properties of B3/S23 that will need some consideration.

Mine assumes that all birth and survival conditions occur in contiguous bands (i.e. deaths can occur from under-population or over-population, but not from an intermediate population, e.g. S35).
Apple Bottom wrote:actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable.

While this will eventually become an issue, the smallest known pseudo-object like this occurs at 32 bits, so it's not an issue now. My own pseudo-still-life filter currently treats these as real objects.
mniemiec

Posts: 1022
Joined: June 1st, 2013, 12:00 am

### Re: Enumerating Still Lifes (in C)

simeks wrote:New result:

Number of on-cells: 28
Strict still lifes: 150613157
Pseudo still lifes: 136655095

And my first result, for subset 25 of the 25- to 30-bitters:

`subset = 25, min = 25Not stable = 15872702118, not canonical = 219570234, not connected = 5250928Number of on-cells:         25Result for subset 25 in (0..99) of search space:Strict still lifes:     135206Pseudo still lifes:      86047Number of on-cells:         26Result for subset 25 in (0..99) of search space:Strict still lifes:     332167Pseudo still lifes:     223376Number of on-cells:         27Result for subset 25 in (0..99) of search space:Strict still lifes:     815550Pseudo still lifes:     574713Number of on-cells:         28Result for subset 25 in (0..99) of search space:Strict still lifes:    2012827Pseudo still lifes:    1490689Number of on-cells:         29Result for subset 25 in (0..99) of search space:Strict still lifes:    4954954Pseudo still lifes:    3857401Number of on-cells:         30Result for subset 25 in (0..99) of search space:Strict still lifes:   12233916Pseudo still lifes:   10020879`

The search took about 6:25 hours, nicely fitting in with Simeks's above estimate:

`Performence timer report:Timer ticks/s: 3435937Elapsed time: 23116485.969 ms`

The resulting files total about 2.55 GiB (144.4 MiB compressed). Which again leaves me wondering, where's the best place to upload/store these results?

Also, if noone else has claimed them yet, I'll do subsets 27-29 next.

EDIT: subset 26 has finished:

`subset = 26, min = 25Not stable = 16291049904, not canonical = 222037575, not connected = 4251140Number of on-cells:         25Result for subset 26 in (0..99) of search space:Strict still lifes:     105034Pseudo still lifes:      66443Number of on-cells:         26Result for subset 26 in (0..99) of search space:Strict still lifes:     258685Pseudo still lifes:     171261Number of on-cells:         27Result for subset 26 in (0..99) of search space:Strict still lifes:     638157Pseudo still lifes:     444129Number of on-cells:         28Result for subset 26 in (0..99) of search space:Strict still lifes:    1581116Pseudo still lifes:    1151166Number of on-cells:         29Result for subset 26 in (0..99) of search space:Strict still lifes:    3926574Pseudo still lifes:    2989489Number of on-cells:         30Result for subset 26 in (0..99) of search space:Strict still lifes:    9761305Pseudo still lifes:    7777677`

The search took a bit longer, roundabout 7 hours, but the resulting files are smaller, 2.06 GiB uncompressed. I've already created an account on GitHub to upload the results to. (This'll take a while, however, I don't have a very fast connection.)
Last edited by Apple Bottom on January 8th, 2017, 8:17 am, edited 1 time in total.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2028
Joined: June 1st, 2009, 4:32 pm

### Re: Enumerating Still Lifes (in C)

calcyman wrote:I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.

And I've updated the counts on the wiki.

Calcyman, could you also submit an update for A056613 (pseudo-still life counts)?
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

mniemiec wrote:
simeks wrote:There is no database of 24 bit still lifes from Mark Niemiec's search, or anyone who has access to the code used for it? It would be interesting to find out if the extra still lifes I've found have any special propertly...

I had the database for 24 bits uploaded temporarily, but I deleted it because the files were a bit too large for GitHub where I placed it.

I can upload it again to a more suitable place, but not until tomorrow when I have a decent internet connection again.

However, since I posted my program to GitHub yesterday, the simplest way would be if you downloaded it from here, compiled it for Linux, or ran the precompiled Windows executable with this command:

> sc128 w 24 24

and you will have the two 24 bit database files generated to the current directory in an hour or two.

mniemiec wrote:
simeks wrote:Since my program reports more results than previously thought, it would be easy to confirm that this is correct if someone would be willing to write an independent script that takes a database from my program and verifies that all generated results are indeed valid 24 bit still lifes and that they are all different.
Would anyone be interested in doing this?

I have a tool that takes a pattern list, and splits it into four separate output buckets - objects, pseudo-objects, quasi-objects (i.e. two adjacent tubs), and non-objects (e.g. constellations). I use this to post-process my own searches, as those output objects and pseudo-objects together. Ideally, the last two categories are always empty, unless something is seriously wrong.

chris_c wrote a tool to verify that all objects in the database are either strict och pseudo still lifes, but without being able to tell those two categories apart. If you can use your tool to verify this, that would be good!

I have also since then written a verification tool with mostly independent code, to verify that all objects in the 24-bit database are unique.
It would still be nice if someone could verify independently that all objects in the 24-bit database are stable and without duplicates. A nice way to do this would be if you were able to compare my database to your 24-bit database and we could figure out by which objects they differ.

mniemiec wrote:This looks like RLE without the header

Yes, I removed the header to keep the size of the databases down, the output would normally look like this:

`x = 8, y = 5, rule = LifeHistory6.A\$5.A.A\$2A3.2A\$A2.2A\$.2A.A!`

mniemiec wrote:
Apple Bottom wrote:actually, thinking about some more now I'm probably not qualified to write a verification tool; I just remembered and looked up the quad pseudo still life, and I'm not at all sure how you'd detect such patterns as pseudo-objects, short of trying to separate their constituent islands in every possible combination and checking if the results are stable.

While this will eventually become an issue, the smallest known pseudo-object like this occurs at 32 bits, so it's not an issue now. My own pseudo-still-life filter currently treats these as real objects.

My search program correctly detects triple/quad pseudo still lifes as pseudo still lifes, and because they are interesting, the program outputs any pseudo still life it finds that can't be partitioned in just two parts, to the console. I've verified that this works by running the small part of the search space for 32 bits that contains the smallest known such pattern. So far Apple Bottom and I have covered 31% of the search space for 30-bit still lifes without finding any smaller triple/quad pseudo still life.

Apple Bottom wrote:The resulting files total about 2.55 GiB (144.4 MiB compressed). Which again leaves me wondering, where's the best place to upload/store these results?

I don't really know... A free Google Drive account can hold 15 GB, but maybe there are better options? Does anyone else know of a good solution?

Apple Bottom wrote:Also, if noone else has claimed them yet, I'll do subsets 27-29 next.

I'll consider subsets 25-49 reserved by you until further notice.
I've completed subsets 0-24 and 50-53. 54-56 are running now.

Apple Bottom wrote:I've already created an account on GitHub to upload the results to. (This'll take a while, however, I don't have a very fast connection.)

A read about GitHub and it seems there's a limit of only 100 MB data for each account. EDIT: Actually, that seems to be the file size limit, but I still don't think GitHub will be suitable.

calcyman wrote:I've updated https://oeis.org/A019473 and https://catagolue.appspot.com/statistics with the corrected 24-bit count together with the new counts up to 28-bit.

Thanks!
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:
Apple Bottom wrote:Also, if noone else has claimed them yet, I'll do subsets 27-29 next.

I'll consider subsets 25-49 reserved by you until further notice.
I've completed subsets 0-24 and 50-53. 54-56 are running now.

[...]
A read about GitHub and it seems there's a limit of only 100 MB data for each account. EDIT: Actually, that seems to be the file size limit, but I still don't think GitHub will be suitable.

OK, I'll consider subsets 25-49 "mine" for now then.

Github does indeed have a 100 MiB file size limit, as I found out much to my chagrin (and only AFTER trying to upload a larger file). However, for 30-bitters, the individual compressed files are well below the limits, so I'm using Github for now anyway. The data files for subsets 25 and 26 are all available here.

In the long run, I still think archive.org is our best bet: able (and willing) to host large amounts of data, dedicated to keeping it permanently accessible to both researchers and lay users, and operating as a non-profit, without competing business interests.

EDIT: subset 27 is done:

`subset = 27, min = 25Not stable = 14882234241, not canonical = 257337784, not connected = 2331392Number of on-cells:         25Result for subset 27 in (0..99) of search space:Strict still lifes:      48777Pseudo still lifes:      20951Number of on-cells:         26Result for subset 27 in (0..99) of search space:Strict still lifes:     126280Pseudo still lifes:      57586Number of on-cells:         27Result for subset 27 in (0..99) of search space:Strict still lifes:     324210Pseudo still lifes:     156643Number of on-cells:         28Result for subset 27 in (0..99) of search space:Strict still lifes:     833059Pseudo still lifes:     426780Number of on-cells:         29Result for subset 27 in (0..99) of search space:Strict still lifes:    2132660Pseudo still lifes:    1155711Number of on-cells:         30Result for subset 27 in (0..99) of search space:Strict still lifes:    5461868Pseudo still lifes:    3132629`

The database files are up on Github.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

I just wrote a converter to convert the RLE format into the LIS format that my own still life enumerator uses, and compared my lists with those generated by s128.exe. (LIS format is a bit more compact; the output files are about 1/3 of the size of the RLE files). The lists are identical, which verifies that not only are the numbers the same, but the acutal generated objects are the same as well (this was highly probable, but not 100% certain until verified).

There is one particular kind of expansion that my program did not handle: expanding a single bit into a new island beginning with a line of 5 adjacent bits. (I had later added a specific fix for this one case, but that fix made one pseudo-still-life disappear, so I didn't consider the change to be robust until I tracked down the source of the error). Without that fix, there were two kinds of objects that would not be found automatically. These were of the form a<-b->c and a->b<-c, where "->" means a line of 5 that requires a 1-bit stabilization, and where b cannot occur at an external corner.

Of the former type, there are 1 22-bit, 5 23-bit, 26 24-bit, and hundreds of 25-bit ones (which is why I never attempted the 25s, until this could be dealt with automatically). Of the latter type, there are 20 24-bit ones.

Your new lists include 6 new still-lifes that were missing from my list. Curiously, all six were in my list of 20 a->b<-c ones to be manually added, dating back to 2011-02-20, but were colored differently than the others (perhaps because I had not yet instantiated them? I am not sure). I had always known that the process of adding the extra still-lifes was error-prone; adding 1 22-bit still-life and 5 23-bit still-lifes manually didn't seem to be a problem, but apparently 46 24-bit ones was.

The one additional pseudo-still-life is one that should have been found, and I have no idea why it would have been missed. It indicates that there is still some kind of subtle bug in my search program.

One good thing that comes from all of this is that, with one single exception that can't be explained, both algorithms produce the same results, and there are no old objects that the new algorithm has missed.
`x = 101, y = 9, rule = B3/S23oo13boo13boo13boobobbo8boo13boo13boo\$obbo5boo4bobbo5boo4bobbo5boo4bob5o8bo14bo14bo9bo\$bboobbobbo7boobbobbo7boobbobbo21bo5boo8bo5boo7boboobb3o\$3bobobobo8bobobobo8bobobobo9bo10boobbobbo8boobbobbo7boobobbo\$3bobbobboo7bobbobboo7bobbobboo7bobo10bobobobo9bobobobo12booboo\$bboo5bobbo4boo5bo7boo5bo9bo11bobbobboo8bobbobboo12boboo\$11boo12bo15bo18boo5bo8boo5bo13bo\$24boo14boo5b5obo15bo15bo10boo\$47bobboboo14boo14boo!`

EDIT:
simeks wrote:In my program I don't grow patterns from a corner, but instead from this start, where the white cell must be on and the red cells are open to define:

When I use the word "corner" in my still-life enumerator, this is what I mean - the leftmost cell on the top row (equivalent to the bottommost cell on the leftmost row in your illustration - rotated 90 degrees from my model).
mniemiec

Posts: 1022
Joined: June 1st, 2013, 12:00 am

### Re: Enumerating Still Lifes (in C)

Subsets 28 and 29 are done:

`subset = 28, min = 25Not stable = 14979308409, not canonical = 237449271, not connected = 4399162Number of on-cells:         25Result for subset 28 in (0..99) of search space:Strict still lifes:      83406Pseudo still lifes:     112513Number of on-cells:         26Result for subset 28 in (0..99) of search space:Strict still lifes:     203316Pseudo still lifes:     288291Number of on-cells:         27Result for subset 28 in (0..99) of search space:Strict still lifes:     493719Pseudo still lifes:     733470Number of on-cells:         28Result for subset 28 in (0..99) of search space:Strict still lifes:    1207706Pseudo still lifes:    1880765Number of on-cells:         29Result for subset 28 in (0..99) of search space:Strict still lifes:    2954346Pseudo still lifes:    4805353Number of on-cells:         30Result for subset 28 in (0..99) of search space:Strict still lifes:    7253577Pseudo still lifes:   12314462`

`subset = 29, min = 25Not stable = 15348642958, not canonical = 224121702, not connected = 5925915Number of on-cells:         25Result for subset 29 in (0..99) of search space:Strict still lifes:     199757Pseudo still lifes:      69639Number of on-cells:         26Result for subset 29 in (0..99) of search space:Strict still lifes:     487139Pseudo still lifes:     184103Number of on-cells:         27Result for subset 29 in (0..99) of search space:Strict still lifes:    1188491Pseudo still lifes:     486392Number of on-cells:         28Result for subset 29 in (0..99) of search space:Strict still lifes:    2914720Pseudo still lifes:    1284669Number of on-cells:         29Result for subset 29 in (0..99) of search space:Strict still lifes:    7142996Pseudo still lifes:    3375082Number of on-cells:         30Result for subset 29 in (0..99) of search space:Strict still lifes:   17548957Pseudo still lifes:    8867024`

Data files are on Github again (or will be soon).

EDIT: subset 30 is done:

`subset = 30, min = 25Not stable = 14755232644, not canonical = 217867764, not connected = 4240169Number of on-cells:         25Result for subset 30 in (0..99) of search space:Strict still lifes:     103411Pseudo still lifes:      79819Number of on-cells:         26Result for subset 30 in (0..99) of search space:Strict still lifes:     251235Pseudo still lifes:     206816Number of on-cells:         27Result for subset 30 in (0..99) of search space:Strict still lifes:     609531Pseudo still lifes:     529905Number of on-cells:         28Result for subset 30 in (0..99) of search space:Strict still lifes:    1489214Pseudo still lifes:    1365701Number of on-cells:         29Result for subset 30 in (0..99) of search space:Strict still lifes:    3636068Pseudo still lifes:    3502094Number of on-cells:         30Result for subset 30 in (0..99) of search space:Strict still lifes:    8934298Pseudo still lifes:    9008027`
Last edited by Apple Bottom on January 9th, 2017, 4:04 pm, edited 1 time in total.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

mniemiec wrote:I just wrote a converter to convert the RLE format into the LIS format that my own still life enumerator uses, and compared my lists with those generated by s128.exe. (LIS format is a bit more compact; the output files are about 1/3 of the size of the RLE files). The lists are identical, which verifies that not only are the numbers the same, but the acutal generated objects are the same as well (this was highly probable, but not 100% certain until verified).

Thanks for doing that! I think it makes a pretty strong case for assuming we've found all 24 bit still lifes now.

mniemiec wrote:The one additional pseudo-still-life is one that should have been found, and I have no idea why it would have been missed. It indicates that there is still some kind of subtle bug in my search program.

I don't know how you feel about sharing source code, but I would find it interesting to take a look.

mniemiec wrote:When I use the word "corner" in my still-life enumerator, this is what I mean - the leftmost cell on the top row (equivalent to the bottommost cell on the leftmost row in your illustration - rotated 90 degrees from my model).

Ok, I misinterpreted your description of it at codercontest.com
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

Subsets 31 and 32 are done:

`subset = 31, min = 25Not stable = 15476376904, not canonical = 235503141, not connected = 5335848Number of on-cells:         25Result for subset 31 in (0..99) of search space:Strict still lifes:      45514Pseudo still lifes:     204512Number of on-cells:         26Result for subset 31 in (0..99) of search space:Strict still lifes:     113090Pseudo still lifes:     518854Number of on-cells:         27Result for subset 31 in (0..99) of search space:Strict still lifes:     278318Pseudo still lifes:    1297059Number of on-cells:         28Result for subset 31 in (0..99) of search space:Strict still lifes:     691597Pseudo still lifes:    3283975Number of on-cells:         29Result for subset 31 in (0..99) of search space:Strict still lifes:    1704229Pseudo still lifes:    8256309Number of on-cells:         30Result for subset 31 in (0..99) of search space:Strict still lifes:    4223567Pseudo still lifes:   20916560`

`subset = 32, min = 25Not stable = 15147671097, not canonical = 251164650, not connected = 4583256Number of on-cells:         25Result for subset 32 in (0..99) of search space:Strict still lifes:     107428Pseudo still lifes:     116785Number of on-cells:         26Result for subset 32 in (0..99) of search space:Strict still lifes:     267093Pseudo still lifes:     299577Number of on-cells:         27Result for subset 32 in (0..99) of search space:Strict still lifes:     665269Pseudo still lifes:     757010Number of on-cells:         28Result for subset 32 in (0..99) of search space:Strict still lifes:    1659748Pseudo still lifes:    1939297Number of on-cells:         29Result for subset 32 in (0..99) of search space:Strict still lifes:    4136943Pseudo still lifes:    4946348Number of on-cells:         30Result for subset 32 in (0..99) of search space:Strict still lifes:   10316211Pseudo still lifes:   12687719`

EDIT:

Subset 33 is done:

`subset = 33, min = 25Not stable = 15580327151, not canonical = 273108705, not connected = 3490538Number of on-cells:         25Result for subset 33 in (0..99) of search space:Strict still lifes:      96701Pseudo still lifes:      41898Number of on-cells:         26Result for subset 33 in (0..99) of search space:Strict still lifes:     243844Pseudo still lifes:     113763Number of on-cells:         27Result for subset 33 in (0..99) of search space:Strict still lifes:     615501Pseudo still lifes:     309894Number of on-cells:         28Result for subset 33 in (0..99) of search space:Strict still lifes:    1549588Pseudo still lifes:     833594Number of on-cells:         29Result for subset 33 in (0..99) of search space:Strict still lifes:    3907337Pseudo still lifes:    2247558Number of on-cells:         30Result for subset 33 in (0..99) of search space:Strict still lifes:    9827256Pseudo still lifes:    6012514`

EDIT 2:

Subset 34:

`subset = 34, min = 25Not stable = 12696432706, not canonical = 250716684, not connected = 1882949Number of on-cells:         25Result for subset 34 in (0..99) of search space:Strict still lifes:      53264Pseudo still lifes:      19909Number of on-cells:         26Result for subset 34 in (0..99) of search space:Strict still lifes:     132072Pseudo still lifes:      56093Number of on-cells:         27Result for subset 34 in (0..99) of search space:Strict still lifes:     328591Pseudo still lifes:     153695Number of on-cells:         28Result for subset 34 in (0..99) of search space:Strict still lifes:     816717Pseudo still lifes:     419791Number of on-cells:         29Result for subset 34 in (0..99) of search space:Strict still lifes:    2037290Pseudo still lifes:    1138699Number of on-cells:         30Result for subset 34 in (0..99) of search space:Strict still lifes:    5093087Pseudo still lifes:    3080753`

EDIT 3: subsets 35 and 36:

`subset = 35, min = 25Not stable = 13449974033, not canonical = 224407969, not connected = 4677979Number of on-cells:         25Result for subset 35 in (0..99) of search space:Strict still lifes:     150902Pseudo still lifes:      83695Number of on-cells:         26Result for subset 35 in (0..99) of search space:Strict still lifes:     369955Pseudo still lifes:     218836Number of on-cells:         27Result for subset 35 in (0..99) of search space:Strict still lifes:     905379Pseudo still lifes:     563656Number of on-cells:         28Result for subset 35 in (0..99) of search space:Strict still lifes:    2220689Pseudo still lifes:    1464846Number of on-cells:         29Result for subset 35 in (0..99) of search space:Strict still lifes:    5449979Pseudo still lifes:    3780671Number of on-cells:         30Result for subset 35 in (0..99) of search space:Strict still lifes:   13397827Pseudo still lifes:    9815235`

`subset = 36, min = 25Not stable = 15526926210, not canonical = 258542785, not connected = 5287097Number of on-cells:         25Result for subset 36 in (0..99) of search space:Strict still lifes:     159142Pseudo still lifes:      99062Number of on-cells:         26Result for subset 36 in (0..99) of search space:Strict still lifes:     390281Pseudo still lifes:     252951Number of on-cells:         27Result for subset 36 in (0..99) of search space:Strict still lifes:     955540Pseudo still lifes:     648751Number of on-cells:         28Result for subset 36 in (0..99) of search space:Strict still lifes:    2347691Pseudo still lifes:    1667496Number of on-cells:         29Result for subset 36 in (0..99) of search space:Strict still lifes:    5764604Pseudo still lifes:    4294379Number of on-cells:         30Result for subset 36 in (0..99) of search space:Strict still lifes:   14186295Pseudo still lifes:   11081870`

EDIT 4: subsets 37 and 38:

`subset = 37, min = 25Not stable = 16005838413, not canonical = 261576264, not connected = 5588534Number of on-cells:         25Result for subset 37 in (0..99) of search space:Strict still lifes:     141549Pseudo still lifes:     116218Number of on-cells:         26Result for subset 37 in (0..99) of search space:Strict still lifes:     345965Pseudo still lifes:     295399Number of on-cells:         27Result for subset 37 in (0..99) of search space:Strict still lifes:     848611Pseudo still lifes:     764187Number of on-cells:         28Result for subset 37 in (0..99) of search space:Strict still lifes:    2087586Pseudo still lifes:    1958030Number of on-cells:         29Result for subset 37 in (0..99) of search space:Strict still lifes:    5153712Pseudo still lifes:    5054253Number of on-cells:         30Result for subset 37 in (0..99) of search space:Strict still lifes:   12709729Pseudo still lifes:   12983493`

`subset = 38, min = 25Not stable = 14670887962, not canonical = 277761653, not connected = 3363721Number of on-cells:         25Result for subset 38 in (0..99) of search space:Strict still lifes:      90779Pseudo still lifes:      47252Number of on-cells:         26Result for subset 38 in (0..99) of search space:Strict still lifes:     229629Pseudo still lifes:     125725Number of on-cells:         27Result for subset 38 in (0..99) of search space:Strict still lifes:     578853Pseudo still lifes:     335652Number of on-cells:         28Result for subset 38 in (0..99) of search space:Strict still lifes:    1451681Pseudo still lifes:     887829Number of on-cells:         29Result for subset 38 in (0..99) of search space:Strict still lifes:    3637245Pseudo still lifes:    2361652Number of on-cells:         30Result for subset 38 in (0..99) of search space:Strict still lifes:    9128205Pseudo still lifes:    6253320`
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

Apple Bottom wrote:EDIT 4: subsets 37 and 38:

I've been running 4 hypertreads of this in the cloud, and now I've completed subsets 50-99 and also 45-49. I'm starting subsets 41-44 now, should be done in about 7 hours.

I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.

I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23. What I would need is a function like:

int evolve_cell (int tile [3] [3], const char *rule_string)

that takes a 3-by-3 grid and a rule string, and returns the correct next cell state for the center cell.
It doesn't have to be fast, because it will only be used to build tables while initializing, and any programming language is fine!
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:I've been running 4 hypertreads of this in the cloud, and now I've completed subsets 50-99 and also 45-49. I'm starting subsets 41-44 now, should be done in about 7 hours.

Nice, that works out really well. I'm done with subset 39, and subset 40 is running right as I'm writing this and should be done in a few hours, so if you are doing/have done all of 0 to 24 and 41 to 99, we should be complete.

I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.

That would be excellent. And if I understand the next bit correctly, "any rule" includes non-/semi-totalistic rules? Even better.

I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23. What I would need is a function like:

int evolve_cell (int tile [3] [3], const char *rule_string)

that takes a 3-by-3 grid and a rule string, and returns the correct next cell state for the center cell.
It doesn't have to be fast, because it will only be used to build tables while initializing, and any programming language is fine!

Hmm, my first instinct there is to treat the neighborhood as a bitstring of length 8 (i.e. a number from 0..255) and look up whether or not the center cell should be alive or dead in the next generation in an array. (No need to "canonicalize" the orientation, either, each subcondition will simply correspond to multiple array elements.)

The array would be hardcoded, so this should be no slower than doing the same for totalistic rules, either. (Famous last words!)

EDIT: Oh yeah, completely forgot, here's the results for subset 39:

`subset = 39, min = 25Not stable = 15671906842, not canonical = 279200823, not connected = 4027698Number of on-cells:         25Result for subset 39 in (0..99) of search space:Strict still lifes:     105606Pseudo still lifes:      82365Number of on-cells:         26Result for subset 39 in (0..99) of search space:Strict still lifes:     256837Pseudo still lifes:     212237Number of on-cells:         27Result for subset 39 in (0..99) of search space:Strict still lifes:     630209Pseudo still lifes:     553134Number of on-cells:         28Result for subset 39 in (0..99) of search space:Strict still lifes:    1544956Pseudo still lifes:    1423014Number of on-cells:         29Result for subset 39 in (0..99) of search space:Strict still lifes:    3795608Pseudo still lifes:    3692340Number of on-cells:         30Result for subset 39 in (0..99) of search space:Strict still lifes:    9342118Pseudo still lifes:    9534378`
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

simeks wrote:I was hoping that someone could help out with one thing though: I'm not familiar at all with rule string such as B2ce3ai/S23.

The following 512-character string encodes complete information about the notation:

`                String lord = "";                lord += "_ceaccaieaeaknja_ceaccaieaeaknjaekejanaairerririekejanaairerriri";                lord += "ccknncqnaijaqnwaccknncqnaijaqnwakykkqyqjrtjnzrqakykkqyqjrtjnzrqa";                lord += "ekirkyrtejerkkjnekirkyrtejerkkjnekejjkrnejecjyccekejjkrnejecjycc";                lord += "anriqyzraariqjqaanriqyzraariqjqajkjywkqkrnccqkncjkjywkqkrnccqknc";                lord += "cnkqccnnkqkqyykjcnkqccnnkqkqyykjaqjwinaarzjqtrnaaqjwinaarzjqtrna";                lord += "ccyyccyennkjyekeccyyccyennkjyekenykknejeirykrikenykknejeirykrike";                lord += "aqrznyirjwjqkkykaqrznyirjwjqkkykaqrqajiarqcnnkccaqrqajiarqcnnkcc";                lord += "intrneriaanajekeintrneriaanajekeajnkaeaeiaccaec_ajnkaeaeiaccaec_";`

For each i in {0, 1, ..., 511}, we have:

• centre cell = (i >> 4) & 1;
• neighbour count = popcount(i & 495);
• shape = lord[i];

I constructed lord algorithmically from a screenshot of the following webpage:

http://www.ibiblio.org/lifepatterns/neighbors2.html

together with the list of row letters. It seems to be correct, since it's in the Catagolue source code for displaying animated SVGs (and no-one has complained about the SVGs).
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2028
Joined: June 1st, 2009, 4:32 pm

### Re: Enumerating Still Lifes (in C)

And finally, here's the results for subset 40:

`subset = 40, min = 25Not stable = 15119821223, not canonical = 261321633, not connected = 3524319Number of on-cells:         25Result for subset 40 in (0..99) of search space:Strict still lifes:      85111Pseudo still lifes:      64568Number of on-cells:         26Result for subset 40 in (0..99) of search space:Strict still lifes:     214399Pseudo still lifes:     173013Number of on-cells:         27Result for subset 40 in (0..99) of search space:Strict still lifes:     533731Pseudo still lifes:     453357Number of on-cells:         28Result for subset 40 in (0..99) of search space:Strict still lifes:    1337707Pseudo still lifes:    1200731Number of on-cells:         29Result for subset 40 in (0..99) of search space:Strict still lifes:    3332824Pseudo still lifes:    3131438Number of on-cells:         30Result for subset 40 in (0..99) of search space:Strict still lifes:    8341582Pseudo still lifes:    8215526`

The data files are uploading to my Github repo right now. And I believe that with this, we're finally done!
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

Apple Bottom wrote:And finally, here's the results for subset 40:
...
The data files are uploading to my Github repo right now. And I believe that with this, we're finally done!

Thanks for helping out!

I've summed up all the output files. Fortunately the sums for 25 to 28 bits match those I've previously reported. Sums for 29 and 30 bits are new:

`Bits    Strict      Psuedo25     9971377     790667626    24619307    2046327427    60823008    5281626528   150613157   13665509529   373188952   35319837930   926068847   914075620`

I've made a copy of all databases uploaded to your GitHub account, and I'll consider how to bundle them up into suitable files for the final database.

Also, there has been no sign of any triple or quad pseudo still life, so it seems the smallest such still life has at least 31 bits (the smallest known has 32 bits).
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:I've summed up all the output files.

Excellent work! I've updated both the pages in the OEIS to include terms up to 30 (as usual, it may take a day or so for these changes to be approved).
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2028
Joined: June 1st, 2009, 4:32 pm

### Re: Enumerating Still Lifes (in C)

simeks wrote:Thanks for helping out!

I've summed up all the output files. Fortunately the sums for 25 to 28 bits match those I've previously reported. Sums for 29 and 30 bits are new:

I've made a copy of all databases uploaded to your GitHub account, and I'll consider how to bundle them up into suitable files for the final database.

Also, there has been no sign of any triple or quad pseudo still life, so it seems the smallest such still life has at least 31 bits (the smallest known has 32 bits).

You're welcome, pardner! *tips hat* Glad to have been able to contribute.

I'll keep the Github repo around for when we inevitably decide to tackle the 31- and 32-bitters (I'd suggest increasing the number of subsets then, however, to e.g. 1000 for the 32-bitters, to offset the increase in both file size and computation time).

I've also updated the relevant pages on the LifeWiki.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

Apple Bottom

Posts: 1024
Joined: July 27th, 2015, 2:06 pm

### Re: Enumerating Still Lifes (in C)

Apple Bottom wrote:
simeks wrote:I have been thinking about writing a version of the still life searcher that will work for any rule defined on the von Neumann neighbourhood. I think it would be pretty easy if I just removed those optimizations that assume the rule is B3/S23.

That would be excellent. And if I understand the next bit correctly, "any rule" includes non-/semi-totalistic rules? Even better.

Yes, and I guess even for anisotropic rules, but that will require changes to the is_canonical function too.

I noticed the new section about Fake still lifes on the wiki.
For the generalized still life searcher I need to find a clear definition of strict/pseudo still lifes versus fake still lifes for non-standard rules. I can think of a possible definition but I guess this must have been considered before in Catagolue for example?

calcyman wrote:The following 512-character string encodes complete information about the notation:
...

calcyman wrote:Excellent work! I've updated both the pages in the OEIS to include terms up to 30 (as usual, it may take a day or so for these changes to be approved).

Thanks!

Apple Bottom wrote:I'll keep the Github repo around for when we inevitably decide to tackle the 31- and 32-bitters (I'd suggest increasing the number of subsets then, however, to e.g. 1000 for the 32-bitters, to offset the increase in both file size and computation time).

I'm playing around with some optimization ideas, and I'll be happy to help out with increasing the number of subsets, seaching some of them, etc. But I think I'll have to leave it to someone else to organize a search to 31-32 bits...

I discovered a small bug in the current version of the still life searcher that only affects searches where <max on cells> is in the range 9 to 12 bits. The division into subsets uses the first 9 on-cells to define which subset is being searched, and counting the subsets didn't work correctly when <max on cells> was too close to that. This is fixed now in an update.
This should not have affected a search such as "sc w 4 23", even though that range is included there, but I'll verify that the database is correct for those bit counts.
simeks

Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

### Re: Enumerating Still Lifes (in C)

simeks wrote:I noticed the new section about Fake still lifes on the wiki.
For the generalized still life searcher I need to find a clear definition of strict/pseudo still lifes versus fake still lifes for non-standard rules. I can think of a possible definition but I guess this must have been considered before in Catagolue for example?

Seems as if "fake still life" is a category that was invented for LifeWiki purposes, for things like the blockade that have names and are clearly stable (P1) but are not strict still lifes, pseudo still lifes, or eaters.

"Fake" doesn't seem like quite the right label -- at least, it implies to me that the object looks stable but actually isn't, or something weird like that. I think the usual label for a blockade would be a "still life constellation". Could "constellation" be used instead of "fake" in Template:Stilllife?

dvgrn
Moderator

Posts: 5627
Joined: May 17th, 2009, 11:00 pm