In Search of Maximum Density Still Lifes
In Search of Maximum Density Still Lifes
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.
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
- 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
Here is one example for 12x12
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
14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
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$!
-
- Posts: 605
- Joined: May 27th, 2016, 1:01 am
Re: In Search of Maximum Density Still Lifes
well well, someone posted faster :/
in any case, here is a symmetric 12x12:
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!
-
- Posts: 6
- Joined: March 10th, 2011, 5:25 pm
Re: In Search of Maximum Density Still Lifes
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?
Re: In Search of Maximum Density Still Lifes
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.yujh wrote: ↑July 1st, 2022, 3:01 pmHere is one example for 12x12I'm curioused what script people used to find the 20*20 and above patterns.Code: Select all
x = 0, y = 0, rule = B3/S23 14b$b2ob2ob2o2b2ob$2bob2obobo2bob$bo5bobobo2b$b4ob2obob2ob$4bobo2bobo2b$b2obobob2obo2b$b2obobo2bob2ob$4bob3o5b$b4o4b4ob$bo3b3obo2bob$2bobo2bobobo2b$b2ob2o2b2ob2ob$14b$!
13x13Code: Select all
x = 0, y = 0, rule = B3/S23 15b$b2ob2obob2ob2ob$b2obob3obob2ob$4bo5bo4b$b3ob5ob3ob$bo2bo5bo2bob$2bobo2b2obobo2b$b2obobobobob2ob$2bobobobobobo2b$bo2bobobobo2bob$b4obobob4ob$7bo7b$b5obob2ob2ob$bo2bob2ob2ob2ob$15b$!
Phil Bookman
Re: In Search of Maximum Density Still Lifes
That was fast work for n=12 and 13. Thanks.
Yearning for n=16, 17, 18...
Yearning for n=16, 17, 18...
Last edited by Book on July 1st, 2022, 6:17 pm, edited 1 time in total.
Phil Bookman
-
- Posts: 1233
- Joined: January 28th, 2022, 7:18 pm
- Location: Planet Z
Re: In Search of Maximum Density Still Lifes
It would be cool if we had a script for this.
Re: In Search of Maximum Density Still Lifes
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.LucasBrown wrote: ↑July 1st, 2022, 4:10 pmThe 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?
Phil Bookman
Re: In Search of Maximum Density Still Lifes
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.
- 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
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$!
Re: In Search of Maximum Density Still Lifes
Phil Bookman
Re: In Search of Maximum Density Still Lifes
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!
Re: In Search of Maximum Density Still Lifes
That's a nice sym 16x16, I've added it. To be clear, the 18x18 "close relative" is not a max density.
Phil Bookman
- 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
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$!
Re: In Search of Maximum Density Still Lifes
Nice sym 17x17! Here it is, tidied up:
Just need 18x18 now to complete n=2...200.
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!
Phil Bookman
Re: In Search of Maximum Density Still Lifes
Just need 18x18 now.Macbi wrote: ↑July 2nd, 2022, 5:00 amLLS 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.
Why brute force won't work: there are about 9x10^95 possibilities.
Phil Bookman
- 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
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!
Re: In Search of Maximum Density Still Lifes
Bravo! We now have at least one example for all n from 2 to 200.
Mission accomplished.
Mission accomplished.
Phil Bookman