In Search of Maximum Density Still Lifes

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

In Search of Maximum Density Still Lifes

Post by Book » July 1st, 2022, 2:13 pm

Please refer to the wiki Density article https://conwaylife.com/wiki/Density.

While the nxn SL max density problem was mathematically solved and solutions published a decade ago, many pattern files for the solutions had not been captured in an accessible place. We now have memorialized these RLEs in the wiki article. Some were already there. Some were reconstructed from images. Most were the result of converting a cache of binary text patterns to plaintext to rles. We now have rles for n=2 to 200 and some over 200 (see article table and external link), with the exception of 12x12, 13x13, 16x16, 17x17 and 18x18. Anyone who can produce an rle for any of these 5 will earn huge kudos.
Phil Bookman

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: In Search of Maximum Density Still Lifes

Post by yujh » July 1st, 2022, 3:01 pm

Here is one example for 12x12

Code: Select all

x = 0, y = 0, rule = B3/S23
14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
I'm curioused what script people used to find the 20*20 and above patterns.
13x13

Code: Select all

x = 0, y = 0, rule = B3/S23
15b$b2ob2obob2ob2ob$b2obob3obob2ob$4bo5bo4b$b3ob5ob3ob$bo2bo5bo2bob$2bobo2b2obobo2b$b2obobobobob2ob$2bobobobobobo2b$bo2bobobobo2bob$b4obobob4ob$7bo7b$b5obob2ob2ob$bo2bob2ob2ob2ob$15b$!

Jormungant
Posts: 605
Joined: May 27th, 2016, 1:01 am

Re: In Search of Maximum Density Still Lifes

Post by Jormungant » July 1st, 2022, 3:09 pm

well well, someone posted faster :/

in any case, here is a symmetric 12x12:

Code: Select all

x = 12, y = 12, rule = LifeHistory
2A.A.2A.2A.A$A.3A.A.A.2A$6.A.A$.6A.A.2A$A6.2A.2A$6A$6.6A$2A.2A6.A$2A.
A.6A$3.A.A$2A.A.A.3A.A$A.2A.2A.A.2A!

LucasBrown
Posts: 6
Joined: March 10th, 2011, 5:25 pm

Re: In Search of Maximum Density Still Lifes

Post by LucasBrown » July 1st, 2022, 4:10 pm

The maximum population of an n × n still life is tabulated in the OEIS at https://oeis.org/A055397. That listing disagrees with table 7 of https://people.eng.unimelb.edu.au/pstuc ... l-life.pdf at n = 24 and n = 26. Could someone who is more familiar with this topic look into that?

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 1st, 2022, 4:29 pm

yujh wrote:
July 1st, 2022, 3:01 pm
Here is one example for 12x12

Code: Select all

x = 0, y = 0, rule = B3/S23
14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
I'm curioused what script people used to find the 20*20 and above patterns.
13x13

Code: Select all

x = 0, y = 0, rule = B3/S23
15b$b2ob2obob2ob2ob$b2obob3obob2ob$4bo5bo4b$b3ob5ob3ob$bo2bo5bo2bob$2bobo2b2obobo2b$b2obobobobob2ob$2bobobobobobo2b$bo2bobobobo2bob$b4obobob4ob$7bo7b$b5obob2ob2ob$bo2bob2ob2ob2ob$15b$!
20 and above were found in a binary text zip file in an obscure corner of a university server. The references (1 and 2 in wiki article) show how they were found for all periods. Not by what we'd call a script.
Phil Bookman

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 1st, 2022, 4:34 pm

That was fast work for n=12 and 13. Thanks.

Yearning for n=16, 17, 18...
Last edited by Book on July 1st, 2022, 6:17 pm, edited 1 time in total.
Phil Bookman

AlbertArmStain
Posts: 1233
Joined: January 28th, 2022, 7:18 pm
Location: Planet Z

Re: In Search of Maximum Density Still Lifes

Post by AlbertArmStain » July 1st, 2022, 6:04 pm

It would be cool if we had a script for this.

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 1st, 2022, 6:43 pm

LucasBrown wrote:
July 1st, 2022, 4:10 pm
The maximum population of an n × n still life is tabulated in the OEIS at https://oeis.org/A055397. That listing disagrees with table 7 of https://people.eng.unimelb.edu.au/pstuc ... l-life.pdf at n = 24 and n = 26. Could someone who is more familiar with this topic look into that?
I believe the errors are in the paper. 24 should be 301; 26 should be 352. I have the patterns they generated for those 2 periods in binary text format that I used to make the RLEs in the PatMan collection and they are as stated here.
Phil Bookman

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: In Search of Maximum Density Still Lifes

Post by Macbi » July 2nd, 2022, 5:00 am

LLS has the option to search for still lifes with population constraints within a given box. Unfortunately the step of enforcing the population constraint is very slow (due to my amaturish implementation). But I should be able to churn out the 16, 17 and 18 cases over the next couple of days, if no one else gets there first.

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: In Search of Maximum Density Still Lifes

Post by yujh » July 2nd, 2022, 2:45 pm

16x16

Code: Select all

x = 0, y = 0, rule = B3/S23
18b$b2ob2ob2obob2ob2ob$b2ob2obob3obob2ob$7bo5bo4b$b4obob6ob2ob$bo2bobobo6b2ob$2bobobobob4o4b$b2obobobobo3b3ob$bo2bobobo2b3o2bob$2bobobob3o2bobo2b$b2obobo4bobob2ob$2bobob6obobo2b$bo2bo8bo2bob$b3ob8ob3ob$4bo8bo4b$b2obob2ob3obob2ob$b2ob2ob2obob2ob2ob$18b$!

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 4th, 2022, 4:07 pm

yujh wrote:
July 2nd, 2022, 2:45 pm
16x16
2 to go! 17 and 18. Then we'll have all n=2...200.
Phil Bookman

xpsd
Posts: 8
Joined: September 27th, 2020, 6:32 am

Re: In Search of Maximum Density Still Lifes

Post by xpsd » July 4th, 2022, 7:24 pm

Another 16x16 and a 18x18 close relative :

Code: Select all

x = 58, y = 27, rule = LifeHistory
3D.D.D5.D.D25.D.D.3D5.D.D$2.D.D.D.D.D.D.D25.D.D3.D.D.D.D.D$3D.3D2.D2.
3D25.3D.3D2.D2.3D$2.D3.D.D.D3.D27.D.D3.D.D3.D$3D3.D7.D27.D.3D7.D5$2A.
2A.A2.E.2E.2E24.2A.2A.A.2E.A.2A.2A$2A.A.3A3E.E.2E24.2A.A.2A.2E.2A.A.
2A$3.A8.E30.A10.A$3A.4A4E.3E24.3A.4A2E4A.3A$A2.A8.E2.E24.A2.A10.A2.A$
.A.A.3A3E.E.E26.A.A.3A2E3A.A.A$2A.A.A4.E.E.2E24.2A.A.A6.A.A.2A$.A.A.A
.AE.E.E.E28.A.A.A2EA.A.A$.A.A.A.2A.A.A.A25.2E.E.E.E2.E.E.E.2E$2A.A.A
4.A.A.2A24.2E.E.E.E2.E.E.E.2E$.A.A.6A.A.A28.A.A.A2EA.A.A$A2.A8.A2.A
24.2A.A.A6.A.A.2A$3A.8A.3A25.A.A.3A2E3A.A.A$3.A8.A27.A2.A10.A2.A$2A.A
.6A.A.2A24.3A.4A2E4A.3A$2A.2A.A2.A.2A.2A27.A10.A$40.2A.A.2A.2E.2A.A.
2A$40.2A.2A.A.2E.A.2A.2A!

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 4th, 2022, 7:46 pm

xpsd wrote:
July 4th, 2022, 7:24 pm
Another 16x16 and a 18x18 close relative :
That's a nice sym 16x16, I've added it. To be clear, the 18x18 "close relative" is not a max density.
Phil Bookman

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: In Search of Maximum Density Still Lifes

Post by yujh » July 6th, 2022, 2:00 pm

17x17

Code: Select all

x = 0, y = 0, rule = B3/S23
19b$bob2ob2obob2ob2obob$b2obobob3obobob2ob$4bobo5bobo4b$b2obob7obob2ob$b2obo9bob2ob$4b11o4b$b3o11b3ob$bo2b11o2bob$3bo11bo3b$bob13obob$b2o13b2ob$4b11o4b$b2obo9bob2ob$b2obob7obob2ob$4bobo5bobo4b$b2obobob3obobob2ob$bob2ob2obob2ob2obob$19b$!

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 6th, 2022, 4:28 pm

Nice sym 17x17! Here it is, tidied up:

Code: Select all

x = 17, y = 17, rule = B3/S23
ob2ob2obob2ob2obo$2obobob3obobob2o$3bobo5bobo$2obob7obob2o$2obo9bob2o$
3b11o$3o11b3o$o2b11o2bo$2bo11bo$ob13obo$2o13b2o$3b11o$2obo9bob2o$2obob
7obob2o$3bobo5bobo$2obobob3obobob2o$ob2ob2obob2ob2obo!
Just need 18x18 now to complete n=2...200.
Phil Bookman

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 7th, 2022, 5:26 pm

Macbi wrote:
July 2nd, 2022, 5:00 am
LLS has the option to search for still lifes with population constraints within a given box. Unfortunately the step of enforcing the population constraint is very slow (due to my amaturish implementation). But I should be able to churn out the 16, 17 and 18 cases over the next couple of days, if no one else gets there first.
Just need 18x18 now.

Why brute force won't work: there are about 9x10^95 possibilities.
Phil Bookman

User avatar
yujh
Posts: 3066
Joined: February 27th, 2020, 11:23 pm
Location: I'm not sure where I am, so please tell me if you know
Contact:

Re: In Search of Maximum Density Still Lifes

Post by yujh » July 8th, 2022, 9:35 am

18x18

Code: Select all

x = 18, y = 18, rule = B3/S23
ob2ob2ob2obob2ob2o$2obobob2ob3obob2o$3bobo8bo$2obob9ob3o$2obo4bo5bo2bo
$3b4o3b3obobo$3o3b4o2bobob2o$o2b2o4bobo2bobo$bobob4o2b4o2bo$2obobo2bob
o4b3o$bobobo2bob5o$o2bob2obo6b3o$4obo2b7o2bo$5bobo6bobo$6ob6obob2o$o5b
o5bobo$bob2obob3obobob2o$2ob2ob2obob2ob2obo!

Book
Posts: 385
Joined: August 28th, 2021, 2:38 pm
Location: California
Contact:

Re: In Search of Maximum Density Still Lifes

Post by Book » July 8th, 2022, 12:41 pm

Bravo! We now have at least one example for all n from 2 to 200.

Mission accomplished.
Phil Bookman

Post Reply