LLSSS min pop search results spam

[hotdogPi]

Please review the moving objects collection when searching for notable known ships.

Thank you, this is what I was looking for, much better than the regular jslife.

I have a slightly tangential question, is there a known value n such that for all possible configurations of n cells (arbitrarily displaced from each other), the complete set of resultant stable patterns (still lifes, oscillators and spaceships) from simulating them until the resultant ash becomes periodic (ie. with apgsearch's pattern separator) is known? LifeWiki:Did you know/52 says "it has been proven that no nine-cell pattern exhibits infinite growth" but dvgrn added it with no citation. I'm not sure how it could be proven without such an exhaustive search being conducted (and thereby spaceships enumerated), does it mean that Amling's population-3 lower bound is superseded (and 9 can be given in all entries, as a baseline)? Does anyone know where this proof was shared?

Here's where the proof was done: viewtopic.php?f=2&t=3604

Yes, everything up to 9 cells was enumerated.

[Sokwe]

Could this method be used to find the smallest completion to a partial result, or is it fundamentally limited to searching the whole space?

Theoretically maybe, practically probably not. Maybe for very small completions and/or for very friendly geometries (like c/2 or c/3).

It would primarily be useful for minimizing the p2 or p3 parts or higher period c/2 and c/3 ships, which isn't very important or interesting. If it's trivial to implement I'd like to be able to use it, but if it requires any amount of actual work then you shouldn't bother. Features like the minimum population for symmetric ships should be a much higher priority.

[amling]

With your current bespoke algorithm, would it be very easy to search up to higher populations under the constraint of symmetry?

That is a goooood idea and it should be pretty easy.

I started some of this last night. Digging through what has run so far...

What I believe will be the worst odd search completed pop 46 in ~13GB memory (and it found the known ship). I've started the other three searches just now and I assume they will complete.

The line of worst even searches was still running when I killed it to move the odd searches to the top. It had completed to pop 54 in ~30GB memory and I project it will take only about 55GB to complete pop 58 so I think there's a good chance I'll be able to do this (even) as well.

TBD 5+ generation geometries...


EDIT: I've just now remembered that I had a question about the table. Some of these are known unique (or exhaustive in the more general case) and some I think are not. As an example I think the c/3 gutter bound of 50 is not know to be exhaustive. We know there are no 49 cell gutter ships from the census I did up to 49 but there could I believe still be other pop 50 gutter ships. Do we want to track this exhaustiveness in the table as well? If we want to it's probably best to do so now while it's all still fresh in our heads.

EDIT: Both odd pop 46 and even pop 58 were completed, details below.

[Sokwe]

I've just now remembered that I had a question about the table. Some of these are known unique (or exhaustive in the more general case) and some I think are not. As an example I think the c/3 gutter bound of 50 is not know to be exhaustive. We know there are no 49 cell gutter ships from the census I did up to 49 but there could I believe still be other pop 50 gutter ships. Do we want to track this exhaustiveness in the table as well? If we want to it's probably best to do so now while it's all still fresh in our heads.

I just recently (in the last 12 hours or so) added a section for exhaustive searches that find spaceships. We can record the results there until someone comes up with a better way to present the data.

[amling]

(about c/4 symmetric min pop searches)

What I believe will be the worst odd search completed pop 46 in ~13GB memory (and it found the known ship). I've started the other three searches just now and I assume they will complete.

The line of worst even searches was still running when I killed it to move the odd searches to the top. It had completed to pop 54 in ~30GB memory and I project it will take only about 55GB to complete pop 58 so I think there's a good chance I'll be able to do this (even) as well.

My fanciest (personal) computer completed c/4 odd pop 46 in ~5.3h and ~13GB memory, finding only the one known pop 46 odd ship, and completed c/4 even pop 58 in ~6.1h and ~56GB memory, finding only the one known pop 58 even ship. The odd search covers the gutter case as well as the found ship has a gutter.

[amling]

(about 3c/6 population bounds)

Limited to 8G it finished 24 and 25, but 26 died. Updated extrapolation is ~8PB for pop 86 and 60GB will cover maybe pop 34.

I did not run all of the searches for pop 25, just the one I assumed would fill the most memory. I think this got put into the wiki's table as ruling out pop 25 ships which it does not (just pop 25 ships which are pop 25 in that hardest-to-search alignment). I had assumed some haphazard middling lower bound was not of interest and so I was not planning on completing these nor actually finding out what 60GB (or 120GB) could do.

[Sokwe]

As an example I think the c/3 gutter bound of 50 is not know to be exhaustive. We know there are no 49 cell gutter ships from the census I did up to 49 but there could I believe still be other pop 50 gutter ships.

On this note, the only known 50-cell c/3 gutter "ships" are actually just two 25-cell ships side-by-side. However, there is a "true" c/3 gutter ship at 52 cells, and this got me wondering what the "true" minimum size is for other speeds and symmetry types. By "true" I mean that the ship is not just two ships side-by-side and in the odd-symmetric case the ship is not also gutter-symmetric. Here is a collection of what I think are the smallest known "true" ships for different speeds (2c/4, 2c/5, c/3, c/4o, c/4d) and symmetry types (gutter, odd, even, even-glide) that do not match the smallest "ship" as measured in the LifeWiki table:

Code: Select all

x = 113, y = 112, rule = B3/S23
51bo$50bobo$50bo$50bo3bo$52bobo49b2o$49b2o2bo49b2o$49bo54bo2bo$48b3o
53b2obo$47bo56b2o3bo$47bo2bo$5o42bo2b2o55bobob2o$o4bo44bo54bobo3bo$o
48b2o45bo8b3o2bo$bo3bo44b2o43b5o6b2o$95bo2b2o2b2o$bo3bo44b2o51b2o$o48b
2o46b2o2b4o$o4bo44bo$5o42bo2b2o47bobo$47bo2bo52bo$47bo53b2o$48b3o50bo$
49bo$49b2o2bo$52bobo$50bo3bo$50bo$50bobo$51bo3$28b2o2b2o39bobo$27b2o
42b2o3b2o$28bob2o39bobo34b2o$4o20bo6bo41bo34bobo$o3bo19bo45bo37bo$o22b
o46b2o3bo35bo$bo2bo19b2obob2o47b2o30bobo$24b2o5b2o40b2o3bo31bobo$5b4o
17b4o44bobo4b2o27bo$4bo2bo21bobo42b7obo27bo$4bo2bo23bo41bo32bo3bo$4bo
2bo21bobo42b7obo22b3obo$5b4o17b4o44bobo4b2o21b2o$24b2o5b2o40b2o3bo24b
2o$bo2bo19b2obob2o47b2o24bo$o22bo46b2o3bo19b3o$o3bo19bo45bo24bo8bo$4o
20bo6bo41bo22bo2b5o$28bob2o39bobo24bo$27b2o42b2o3b2o21b2o$28b2o2b2o39b
obo13$4o$o3bo$o24b2o$bo3bo18b3o$6bo16bo3b3o$3b2ob2o16b2o2bobo5bo$3bo
21bo2bob2o4b3o$3bo4b2o18b2ob2o2bo2bo$4b2ob2obo18bo3bo2bo$8bo21b3o3bo$
31bo$31bo$8bo21b3o3bo$4b2ob2obo18bo3bo2bo$3bo4b2o18b2ob2o2bo2bo$3bo21b
o2bob2o4b3o$3b2ob2o16b2o2bobo5bo$6bo16bo3b3o$bo3bo18b3o$o24b2o$o3bo$4o
13$3b2o$bo4bo$o$o5bo$6o2$5bobo$4bo2bo$5bo$3b2o2bo$bo5bo$o$o5bo$6o!

I'm not sure if it's feasible to have LLSSS confirm any of these.

[amling]

(about gutter ships)

I'm not sure if it's feasible to have LLSSS confirm any of these.

Unfortunately the current exhaustive population search absolutely does not work once you have enough population to make two separate ships. I do not have any good ideas about how to terminate the search once it has gone too far and is only making disconnected stuff. When the bound isn't enough for two separate ships eventually there is a global disconnect which is what the current code detects to halt.

It's possible we could translate the population bound to an absolute upper bound on search depth but I think it would be bad (large) and searches would probably fill memory first and die. The most obvious bound is something like a number of Y rows longer than 3 times the population itself at which point any partial would have to have a gap of 2 Y rows. You might be able to do better than that by analyzing viable island sizes but I don't think this is gonna be doable.

Also the search is gonna spew out constant useless disconnected hits the whole way as LLSSS has no notion of connectedness. Even if we thought the searches would make it to the huge depth limit it's gonna be a bunch more work to analyze for connectedness and discard these.

[Sokwe]

Unfortunately the current exhaustive population search absolutely does not work once you have enough population to make two separate ships.

To make sure I'm understanding this correctly in the symmetric case, does that mean the search breaks down once you have enough population for just one ship on one side (there would, of course, be a mirrored ship on the other side)? I would presume so, since these ships could then be placed arbitrarily far apart without an obvious reason why they couldn't be connected by some short wide tagalong.

Edit: by the way, the smallest known 2c/5 and c/4o "true" odd-symmetric ships posted above are still smaller than any two ships side-by-side, so those could presumably be checked. However, it would be a difficult search (possibly just inside or just outside the capability of your hardware) due to the high populations.

[amling]

Unfortunately the current exhaustive population search absolutely does not work once you have enough population to make two separate ships.

To make sure I'm understanding this correctly in the symmetric case, does that mean the search breaks down once you have enough population for just one ship on one side (there would, of course, be a mirrored ship on the other side)? I would presume so, since these ships could then be placed arbitrarily far apart without an obvious reason why they couldn't be connected by some short wide tagalong.

I think I may have confused myself about the symmetric case. Finding a mirrored single asymmetric ship is fine and it will refuse to generate all spacings of it (it won't generate anything with two full blank columns either). Once it hits the population of four asymmetric ships or two symmetric ships I think it (first) won't be able to terminate any more.

I'm away from computers and somewhat distracted by real life at the moment. When I am more reasonably back at the wheel I will make sure I have this figured out and see what I can do.

[amling]

Here is a collection of what I think are the smallest known "true" ships for different speeds (2c/4, 2c/5, c/3, c/4o, c/4d) and symmetry types (gutter, odd, even, even-glide) that do not match the smallest "ship" as measured in the LifeWiki table:

Code: Select all

x = 113, y = 112, rule = B3/S23
51bo$50bobo$50bo$50bo3bo$52bobo49b2o$49b2o2bo49b2o$49bo54bo2bo$48b3o
53b2obo$47bo56b2o3bo$47bo2bo$5o42bo2b2o55bobob2o$o4bo44bo54bobo3bo$o
48b2o45bo8b3o2bo$bo3bo44b2o43b5o6b2o$95bo2b2o2b2o$bo3bo44b2o51b2o$o48b
2o46b2o2b4o$o4bo44bo$5o42bo2b2o47bobo$47bo2bo52bo$47bo53b2o$48b3o50bo$
49bo$49b2o2bo$52bobo$50bo3bo$50bo$50bobo$51bo3$28b2o2b2o39bobo$27b2o
42b2o3b2o$28bob2o39bobo34b2o$4o20bo6bo41bo34bobo$o3bo19bo45bo37bo$o22b
o46b2o3bo35bo$bo2bo19b2obob2o47b2o30bobo$24b2o5b2o40b2o3bo31bobo$5b4o
17b4o44bobo4b2o27bo$4bo2bo21bobo42b7obo27bo$4bo2bo23bo41bo32bo3bo$4bo
2bo21bobo42b7obo22b3obo$5b4o17b4o44bobo4b2o21b2o$24b2o5b2o40b2o3bo24b
2o$bo2bo19b2obob2o47b2o24bo$o22bo46b2o3bo19b3o$o3bo19bo45bo24bo8bo$4o
20bo6bo41bo22bo2b5o$28bob2o39bobo24bo$27b2o42b2o3b2o21b2o$28b2o2b2o39b
obo13$4o$o3bo$o24b2o$bo3bo18b3o$6bo16bo3b3o$3b2ob2o16b2o2bobo5bo$3bo
21bo2bob2o4b3o$3bo4b2o18b2ob2o2bo2bo$4b2ob2obo18bo3bo2bo$8bo21b3o3bo$
31bo$31bo$8bo21b3o3bo$4b2ob2obo18bo3bo2bo$3bo4b2o18b2ob2o2bo2bo$3bo21b
o2bob2o4b3o$3b2ob2o16b2o2bobo5bo$6bo16bo3b3o$bo3bo18b3o$o24b2o$o3bo$4o
13$3b2o$bo4bo$o$o5bo$6o2$5bobo$4bo2bo$5bo$3b2o2bo$bo5bo$o$o5bo$6o!

I'm not sure if it's feasible to have LLSSS confirm any of these.

I think I've convinced myself problems occur at twice the pop of a symmetric ship (or four times an asymmetric ship since it can be paired with itself to produce what LLSSS would consider a symmetric ship). Some of the above are thus in range and I think some are not. I'll start working through them...

2c/4 odd to pop 32 completed very quickly with very little memory, finding only *WSSes and that one pop 32 ship (I may have seen someone call it "big A" before?).

2c/4 gse to pop 32 also completely quickly, finding only *WSSes and that one pop 32 ship. EDIT: Nope, nope, nope, this is wrong: the weighting doesn't make sense for gse where I need to not double the weights of reflected columns but rather count two different generations of pattern towards two different generations of bounds. This isn't gonna be fixable without some rather finicky hacking on the code.

EDIT: 2c/4 even to pop 48 is out of range (max is 4x9-1 = 35).

EDIT: c/3 odd to pop 52 finished pretty quickly, finding only silly pairs, dart, and that one "true gutter" pop 52 ship.

[amling]

I've run a few days of c/4 odd searches now on my best machine and I extrapolate the presumed worst alignment (of four) will reach 99.5GB and take 5.3 days for pop 61. Add the other three alignments and I'm guessing this would take weeks. I'm gonna put this on hold and try to remember to bring it back next time I go on vacation and want a very long search to leave running (should be 2023/12/20).

[Sokwe]

2c/4 odd to pop 32 completed very quickly with very little memory...

2c/4 even to pop 48 is out of range (max is 4x9-1 = 35).

c/3 odd to pop 52 finished pretty quickly

Thanks! If you find the time, I would appreciate if you could run the searches up to period 4 that are likely to complete quickly (e.g., 2c/4 odd pop 35, 2c/4 even pop 34, c/3 odd/even pop 54+). Obviously this is a low priority, but there aren't any other programs I know of that can run an unconstrained population search so I'd really like whatever results we can get.

[amling]

...2c/4 odd pop 35, 2c/4 even pop 34, c/3 odd/even pop 54+...

2c/4 even pop 35 completed quickly in all phases and found only *WSSes.

2c/4 odd pop 35 completed quickly enough in all phases and found only *WSSes (including gutter-touching versions), Big A and X66 (EDIT: fixed names based on wiki pages linked from catalogue).

Based on some testing I believe c/3 odd to pop 67 is in easily in range, even on my smallest computer (pop 68 won't work due to double of dart). Ditto c/3 even pop 87 (pop 88 NG due to double of pop 44 ship). Stay tuned.

I would be interested to see the counts for whatever population you could reach for p2 ships, If you ever feel like running the searches and deduplicating the results.

I've improved the code to be able to do its own counting and deduping as it goes without outputting tens of thousands of useless spaceships and I've verified the counts match to pop 90. Based on some scale testing I believe c/2 asymmetric pop 127 is in range, but it's gonna take my fanciest machine (which it is currently in line to run on, behind some other searches).

[amling]

Based on some testing I believe c/3 odd to pop 67 is in easily in range, even on my smallest computer (pop 68 won't work due to double of dart). Stay tuned.

c/3 odd to pop 67 combined took a little over an hour (on a laptop under high research computing contention with other stuff), maxing out at 1.44 GB (and like half of that is stupid overhead, not actual program data structures).

Populations of final collection are: 1x34, 1x52, 1x54, 1x56, 4x58, 1x59, 1x60, 4x62, 2x63, 1x64, 3x65, 4x66, 2x67.

In population order:

Code: Select all

#C [[ TRACK 0 -1/3 ]]
x = 41, y = 633, rule = B3/S23
7bo$6bobo$5bo3bo$6b3o2$4b2o3b2o$2bo3bobo3bo$b2o3bobo3b2o$o5bobo5bo$bob
2obobob2obo15$8b3o7b3o$7bo13bo$5b3o4bo3bo4b3o$b3obobob5ob5obobob3o$o9b
o2bobo2bo9bo$bo2bo19bo2bo$5bo17bo$3b2o19b2o15$b3o11b3o$o17bo$bo2b3ob3o
b3o2bo$3bo2bobobobo2bo$5b2obobob2o$5bo2bobo2bo$4bo3bobo3bo$8bobo$6bo5b
o2$6b7o$5b2o5b2o16$5bo19bo$b3ob3o15b3ob3o$o6b2o13b2o6bo$b2o3bo2bo11bo
2bo3b2o2$10b3ob3ob3o$9bo2bobobobo2bo$10b3o5b3o$9b2o4bo4b2o$14bobo15$9b
o$8bobo$7bo3bo$8b3o2$2bo3b2o3b2o3bo$b4o3bobo3b4o$o3bo3bobo3bo3bo$bo6bo
bo6bo$4b3obobob3o$8bobo$3bo3bo3bo3bo$2bo13bo$2bo13bo$4bo9bo$2b2o11b2o
15$b2ob3o17b3ob2o$b2o4b2o5b3o5b2o4b2o$o2bobo3bo4b3o4bo3bobo2bo$7b3o2bo
5bo2b3o$9b2o3bobo3b2o$10bo9bo$10bo2bobobo2bo$12b2obob2o15$6b3o5b3o5b3o
$2bob2o3bo4b3o4bo3b2obo$b3o3b3o2bo5bo2b3o3b3o$o3bo4b2o3bobo3b2o4bo3bo$
bo8bo9bo8bo$10bo2bobobo2bo$12b2obob2o15$7bo15bo$5b4o13b4o$b2ob2o3bo11b
o3b2ob2o$b2o2bo19bo2b2o$o2bo6b3ob3ob3o6bo2bo$9bo2bobobobo2bo$10b3o5b3o
$9b2o4bo4b2o$14bobo15$9bo$8bobo$7bo3bo2$b2ob4o3b4ob2o$b2o4b2ob2o4b2o$o
2bob3o3b3obo2bo2$8bobo$6bobobobo$2b2obo7bob2o$2b2o4bobo4b2o$bo3b2o5b2o
3bo15$11b3o7b3o$10bo13bo$8b3o4bo3bo4b3o$7b2obob5ob5obob2o$2bo3bo6bo2bo
bo2bo6bo3bo$b4o25b4o$o3bo25bo3bo$bobo2bo21bo2bobo$5bo23bo15$b2o11b2o$b
2ob2o5b2ob2o$o3b2o5b2o3bo$obo3b2ob2o3bobo$4bo2bobo2bo$5bobobobo$2b2obo
bobobob2o$2bo2bobobobo2bo$7bobo$3obo7bob3o$6b2ob2o15$5b3o9b3o$8bo7bo$
8b3o3b3o$b2ob3obobo3bobob3ob2o$b2o3bo4bobo4bo3b2o$o2bo6bo3bo6bo2bo2$8b
2o5b2o$9bo5bo$10bo3bo$8bo7bo$12bo$8b2ob3ob2o$11bobo15$5bo19bo$b3ob3o
15b3ob3o$o6b2o13b2o6bo$b2o3bo2bo11bo2bo3b2o$11b3o3b3o$10bo3bobo3bo$10b
obobobobobo$9b3o2bobo2b3o$13b2ob2o$11bo2bobo2bo$13bo3bo15$9bo15bo$2bo
5b4o11b4o5bo$bobo3bo3b2o9b2o3bo3bobo$o3bo3bo4bo2b3o2bo4bo3bo3bo$b2obo
5bo5b3o5bo5bob2o$6bobo4bo2bobo2bo4bobo$8bo4b2o5b2o4bo$10bo13bo$9bo15bo
15$7b3obobob3o$5b3ob2obob2ob3o$b3obo5bobo5bob3o$o6bo3bobo3bo6bo$bo2bo
6bobo6bo2bo$5bo3bo5bo3bo$3b2o5b2ob2o5b2o$10b2ob2o$11bobo2$10b2ob2o15$
2bob2ob3o4bobobobo4b3ob2obo$b2ob2o4b3ob2obob2ob3o4b2ob2o$o2bobo2bo7bob
o7bo2bobo2bo$bo5bo4b2o2bobo2b2o4bo5bo$16bobo$12bo9bo$12bobo5bobo15$7bo
15bo$5b4o13b4o$b2ob2o3bo11bo3b2ob2o$b2o2bo5b3o3b3o5bo2b2o$o2bo6bo3bobo
3bo6bo2bo$10bobobobobobo$9b3o2bobo2b3o$13b2ob2o$11bo2bobo2bo$13bo3bo
15$10bo$b3o5bobo5b3o$o7bo3bo7bo$bo2b3o7b3o2bo$3bo2bob2ob2obo2bo$5b2obo
3bob2o$5bo9bo$5bob2o3b2obo$7b2o3b2o$7bobobobo2$7b2o3b2o2$7bo5bo$7bo5bo
$6bobo3bobo$8bo3bo15$10bo$b3o5bobo5b3o$o7bo3bo7bo$bo2b3o7b3o2bo$3bo2bo
b2ob2obo2bo$5b2obo3bob2o$5bo9bo$5bob2o3b2obo$7b2o3b2o$7bobobobo2$7b2o
3b2o2$8bo3bo$8bo3bo$7bobobobo$7bo5bo15$10bo$b3o5bobo5b3o$o7bo3bo7bo$bo
2b3o7b3o2bo$3bo2bob2ob2obo2bo$5b2obo3bob2o$5bo9bo$5bob2o3b2obo$7b2o3b
2o$7bobobobo2$8b2ob2o2$8bo3bo$8bo3bo$7bobobobo$9bobo15$7bo5bo$5b4o3b4o
$b2ob2o3bobo3b2ob2o$b2o2bo3bobo3bo2b2o$o2bo5bobo5bo2bo$8b2ob2o$7b3ob3o
$5bo3bobo3bo$4b2o3bobo3b2o$3bo5bobo5bo$4bob2obobob2obo15$11bo5bo$9b4o
3b4o$8b2o3bobo3b2o$5bo5bobobobo5bo$b3ob2o3b2obobob2o3b2ob3o$o5bo3b2obo
bob2o3bo5bo$b2o4bobob3ob3obobo4b2o$11bobobobo15$10b3o5b3o$9bo3b2ob2o3b
o$9bobo2bobo2bobo$8b2o2b2o3b2o2b2o$7b2o2bobo3bobo2b2o$5b2obo4bo3bo4bob
2o$4bobo17bobo$b2obo3b2o11b2o3bob2o$b2obo21bob2o$bobo23bobo15$5bo29bo$
b3ob3o25b3ob3o$o6b2o5b3o7b3o5b2o6bo$b2o3bo2bo3bo13bo3bo2bo3b2o$11b3o4b
o3bo4b3o$11bobob5ob5obobo$9bo6bo2bobo2bo6bo$10bo19bo15$8bo17bo$7b5ob2o
b3ob2ob5o$2bo3bo3b2ob2o5b2ob2o3bo3bo$b4o9bobobobo9b4o$o3bo10b2ob2o10bo
3bo$bobo2bo5b2o7b2o5bo2bobo$5bo7bo7bo7bo$13bo7bo15$17b3o$17b3o$16bo3bo
2$15bo5bo$5bobobob6obob6obobobo$b3ob2obob2obo9bob2obob2ob3o$o6bobo17bo
bo6bo$b2o3bo2bo17bo2bo3b2o$8bobo15bobo$10bo15bo!

[amling]

It has occurred to me that eventually you may have to get very specific in your definition of strict odd ship as things can get a bit touchy...

Code: Select all

#C [[ TRACK 0 -1/3 ]]
x = 35, y = 10, rule = B3/S23
8b3o13b3o$2o5bo3b2o9b2o3bo5b2o$2obo3bobo3bo7bo3bobo3bob2o$3o2bobo2b3o
9b3o2bobo2b3o$2bo2b2o4b3o7b3o4b2o2bo$7b2ob3o2bo3bo2b3ob2o$3bobo9bo3bo
9bobo$3bo12bobo12bo$10b4o2bobo2b4o$12bo9bo!

Is it two ships because they could exist as they are separately? Is it one ship because they are connected by an over-population non-birth with 4 neighbors? Historically analyzers I have written would judge them as the latter (connected), perhaps only because I could not think of how to clearly define and/or efficiently analyze for "could subset exist independently"...

[Sokwe]

Is it two ships because they could exist as they are separately? Is it one ship because they are connected by an over-population non-birth with 4 neighbors?

That's two ships forming a pseudo-spaceship.

Edit: you probably shouldn't worry about filtering such objects automatically. Most of your min pop searches would find so few pseudo-spaceships that they could easily be filtered by hand.

[Haycat2009]

Can we prove that 25P3H1V0.1 and 25P3H1V0.2 are the smallest c/3 spaceships?

[confocaloid]

Can we prove that 25P3H1V0.1 and 25P3H1V0.2 are the smallest c/3 spaceships?

(edit: for period 3 only; see the post by Sokwe below) I think this is already confirmed:

Code: Select all

[...]
#C The following table shows the mininum number of cells for
#C  spaceships of all types with period < 10.  Those marked [*] are
#C  known to be best possible.
#C
#C  (1,0)c/2  64 cells [*]            Dean Hickerson       28 Jul 1989
#C  (1,0)c/3  25 cells [*]            Dean Hickerson          Aug 1989
[...]

[Sokwe]

Can we prove that 25P3H1V0.1 and 25P3H1V0.2 are the smallest c/3 spaceships?

If you mean the smallest period-3 c/3 spaceships, this has already been shown as confocaloid noted. If you mean c/3 spaceships of any period, then we most certainly cannot prove these are the smallest. To do so would I think essentially require us to enumerate all objects up to 24 cells, which is quite impossible given the combinatorial explosion caused by methuselahs that interact by shooting gliders at each other. I think the only result we (that is, Keith Amling) can currently prove is that there are no (2,0)c/6 ships up to 25 cells, but that would probably be a difficult search with little payoff, so it isn't likely to be prioritized.

[amling]

...c/3 even pop 87...

All phases completed in a combined 4.6 hours using up to 4.7 GB. Final populations were 1x44, 1x60, 1x64, 2x66, 1x70, 1x74, 4x76, 6x78, 3x80, 2x82, 3x84, 4x86 (29 total ships). In population order:

Code: Select all

#C [[ TRACK 0 -1/3 ]]
x = 50, y = 776, rule = B3/S23
5b2o$b2obo2bob2o$b2o6b2o$bobo4bobo$3b2o2b2o$2b2ob2ob2o$4bo2bo$2bo6bo$
2bo6bo2$2b8o$b2o6b2o16$7b2o$3b2obo2bob2o$3b2o6b2o$3bobo4bobo$5b2o2b2o$
4b2ob2ob2o$6bo2bo$5bo4bo$b3ob2o2b2ob3o$o5bo2bo5bo$bo2b3o2b3o2bo$5bob2o
bo$3b2o6b2o15$2bob2ob3o4b2o4b3ob2obo$b2ob2o4b3ob2ob3o4b2ob2o$o2bobo2bo
12bo2bobo2bo$bo5bo4b2o2b2o4bo5bo2$12bo4bo$11b8o2$11bo6bo2$11b3o2b3o16$
16b2o$5bo6b2obo2bob2o6bo$b3ob3o4b2o6b2o4b3ob3o$o6b2o2bobobo2bobobo2b2o
6bo$b2o3bo4b2o8b2o4bo3b2o$7bo18bo$11bo10bo$7b2o16b2o2$6bo20bo$7b2o16b
2o$6bobo16bobo15$16b2o$5bo6b2obo2bob2o6bo$b3ob3o4b2o6b2o4b3ob3o$o6b2o
2bobobo2bobobo2b2o6bo$b2o3bo4b2o8b2o4bo3b2o$7bo18bo$11bo10bo$7b2o16b2o
2$9bo14bo$7b2o16b2o$7bobo14bobo15$7b2obo3b2o3bob2o$7b2o2bobo2bobo2b2o$
b2o4b2o2bo6bo2b2o4b2o$b2ob2o7bo2bo7b2ob2o$o3b2o7b4o7b2o3bo$4b2o5b8o5b
2o2$10bo8bo$11bo6bo$12bob2obo2$11b2o4b2o15$5bob2o28b2obo$b3ob2obob2o
22b2obob2ob3o$o6b2o2bo10b2o10bo2b2o6bo$b2o3bo3bobo5b2obo2bob2o5bobo3bo
3b2o$13b2o3b2o6b2o3b2o$14bo2bobobo2bobobo2bo$13bo3b2o8b2o3bo$14bo16bo$
17bo10bo15$7b2o$3b2obo2bob2o$3b2o6b2o$3bobo4bobo$5b2o2b2o$4b2ob2ob2o$
6bo2bo$4bo6bo$4bo6bo2$4b8o$3b2o6b2o2$7b2o$6bo2bo$b3o2b4o2b3o$obob3o2b
3obobo$bo4bo2bo4bo$4b2o4b2o15$5bob2obo3b2o3bob2obo$b3ob2obo2bobo2bobo
2bob2ob3o$o6b2o2bo6bo2b2o6bo$b2o3bo6bo2bo6bo3b2o$13b4o$11b8o$8b2o10b2o
$8b2o10b2o$7bo14bo$10b2o2b2o2b2o$10bo8bo$11bo6bo$10bo8bo15$5bob2obo3b
2o3bob2obo$b3ob2obo2bobo2bobo2bob2ob3o$o6b2o2bo6bo2b2o6bo$b2o3bo6bo2bo
6bo3b2o$13b4o$12b6o$11bo6bo2$10bo8bo$10b2o6b2o$12bob2obo$14b2o$10b3o4b
3o$12bo4bo$12bo4bo15$8b3o10b2o10b3o$7bo9b2obo2bob2o9bo$5b3o4bo4b2o6b2o
4bo4b3o$b3obobob5o2bobobo2bobobo2b5obobob3o$o9bo2bo2b2o8b2o2bo2bo9bo$b
o2bo34bo2bo$5bo10bo10bo10bo$3b2o34b2o15$7bo18bo$6b2ob5ob4ob5ob2o$5b2o
5bo8bo5b2o$3b2obobob2o4b2o4b2obobob2o$b2obo2bo2bobo2bo2bo2bobo2bo2bob
2o$o3bo5bobo8bobo5bo3bo$bobo8bo2bo2bo2bo8bobo$12bob6obo17$16b2o$5bo6b
2obo2bob2o6bo$b3ob3o4b2o6b2o4b3ob3o$o6b2o2bobobo2bobobo2b2o6bo$b2o3bo
4b2o8b2o4bo3b2o$7bo18bo$12bo8bo$7b2o4b2o4b2o4b2o2$6bo4bo2bo4bo2bo4bo$
7b2o3bobo4bobo3b2o$6bobo16bobo15$b2ob3o22b3ob2o$b2o4b2o18b2o4b2o$o2bob
o3bo16bo3bobo2bo$7b3o16b3o$9b4o4b2o4b4o$9bo3b3ob2ob3o3bo$10b2o12b2o$
15b2o2b2o2$15bo4bo$14b8o2$14bo6bo2$14b3o2b3o16$6b3o18b3o$2bob2o3bo16bo
3b2obo$b3o3b3o16b3o3b3o$o3bo4b4o4b2o4b4o4bo3bo$bo7bo3b3ob2ob3o3bo7bo$
10b2o12b2o$15b2o2b2o2$15bo4bo$14b8o2$14bo6bo2$14b3o2b3o16$10b3o4b2o4b
3o$9bo3b3ob2ob3o3bo$9b3o12b3o$6b4o5b2o2b2o5b4o$2bob2o3bo16bo3b2obo$b3o
3b2o6bo4bo6b2o3b3o$o3bo9b8o9bo3bo$bo32bo$14bo6bo2$14b3o2b3o16$7b2o28b
2o$7b2ob2o22b2ob2o$b2o4b2o2bo10b2o10bo2b2o4b2o$b2ob2o4bobo5b2obo2bob2o
5bobo4b2ob2o$o3b2o7b2o3b2o6b2o3b2o7b2o3bo$4b2o8bo2bobobo2bobobo2bo8b2o
$13bo3b2o8b2o3bo$14bo16bo$17bo10bo15$6b2o$2b2obo2bob2o$2b2o6b2o$2bobo
4bobo$4b2o2b2o$3b2ob2ob2o$5bo2bo$3bo6bo$3bo6bo2$3b8o$2b2o6b2o3$5bo2bo$
2bob2o2b2obo$b5o2b5o$o3bob2obo3bo$bo2bo4bo2bo$4bo4bo$2bo8bo$3b2o4b2o
15$7b2obo3b2o3bob2o$7b2o2bobo2bobo2b2o$b2o4b2o2bo6bo2b2o4b2o$b2ob2o7bo
2bo7b2ob2o$o3b2o7b4o7b2o3bo$4b2o5b8o5b2o$8b2o10b2o$8b2o10b2o$7bo14bo$
10b2o2b2o2b2o$10bo8bo$11bo6bo$10bo8bo15$7b2obo3b2o3bob2o$7b2o2bobo2bob
o2b2o$b2o4b2o2bo6bo2b2o4b2o$b2ob2o7bo2bo7b2ob2o$o3b2o7b4o7b2o3bo$4b2o
6b6o6b2o$11bo6bo2$10bo8bo$10b2o6b2o$12bob2obo$14b2o$10b3o4b3o$12bo4bo$
12bo4bo15$5bo24bo$3b3ob3o16b3ob3o$2b2o6bo14bo6b2o$bo3bob2obo3bob4obo3b
ob2obo3bo$bo11b2ob4ob2o11bo$4b4obo6bo2bo6bob4o$b3o3bo2b2o2bo6bo2b2o2bo
3b3o$2o6bo2bo12bo2bo6b2o$12bo10bo15$14bob4obo$13b2ob4ob2o$12bo4b2o4bo$
16b4o$14b2o4b2o$15bo4bo$7bo6bobo2bobo6bo$5b3ob4o10b4ob3o$b2ob2o2bobob
2o2b4o2b2obobo2b2ob2o$b2o2bo3bo16bo3bo2b2o$o2bo9bo8bo9bo2bo15$10b2o$6b
2obo2bob2o$6b2o6b2o$6bobo4bobo$8b2o2b2o$7b2ob2ob2o$9bo2bo$7bo6bo$7bo6b
o2$7b8o$6b2o6b2o2$10b2o$9bo2bo$9b4o$6b4o2b4o$2bob2o3bo2bo3b2obo$b3o3b
2o4b2o3b3o$o3bo12bo3bo$bo18bo15$11b2o$7b2obo2bob2o$7b2o6b2o$7bobo4bobo
$9b2o2b2o$8b2ob2ob2o$10bo2bo$8bo6bo$8bo6bo2$8b8o$7b2o6b2o3$10bo2bo$10b
o2bo$10bo2bo$5bo3b6o3bo$b3ob4o6b4ob3o$o6b2o6b2o6bo$b2o3bo10bo3b2o15$
11b3o10b2o10b3o$10bo9b2obo2bob2o9bo$8b3o4bo4b2o6b2o4bo4b3o$7b2obob5o2b
obobo2bobobo2b5obob2o$2bo3bo6bo2bo2b2o8b2o2bo2bo6bo3bo$b4o40b4o$o3bo
14bo10bo14bo3bo$bobo2bo36bo2bobo$5bo38bo15$7b4o6b4o$3bob2obobo6bobob2o
bo$2b3o4bo2b4o2bo4b3o$bo3bo6b4o6bo3bo$2bo8bo4bo8bo2$10bo6bo$9b3ob2ob3o
$7b2o10b2o$7b2o10b2o$b2o4b2o10b2o4b2o$b2ob2o16b2ob2o$o3b2o16b2o3bo$4b
2o16b2o15$6b3o16b3o$2bob2o3bo14bo3b2obo$b3o3bobo3bo6bo3bobo3b3o$o3bo4b
2obobo4bobob2o4bo3bo$bo7b2o4bo2bo4b2o7bo$11bo10bo$13bob4obo$13bo6bo$
11b2o8b2o$8b2obobo6bobob2o$8b2obobo2b2o2bobob2o$8bobo3bob2obo3bobo16$
19b2o$12b3o2b2o2b2o2b3o$15bo8bo$10bo4bo8bo4bo$10b2ob3o8b3ob2o$10bobob
12obobo$7b2o2b3o2bobo2bobo2b3o2b2o$4b2ob2o2bo16bo2b2ob2o$b4o2bo24bo2b
4o$o4bo28bo4bo$b2o34b2o15$5bob2o28b2obo$b3ob2obob2o22b2obob2ob3o$o6b2o
2bo10b2o10bo2b2o6bo$b2o3bo3bobo5b2obo2bob2o5bobo3bo3b2o$13b2o3b2o6b2o
3b2o$14bo2bobobo2bobobo2bo$13bo3b2o8b2o3bo$14bo16bo$18bo8bo$19b2o4b2o
2$17bo2bo4bo2bo$18bobo4bobo!

[amling]

I'm about to head out of town again for about two weeks. In the meantime the worst phase (of two) for c/2 asymmetric to pop 127 is running on my fanciest computer (and already has been for two weeks!). Examining time/memory patterns for smaller runs more closely and trying to estimate from the log so far I think it probably has another two weeks (and based on other extrapolation, the easier of the two phases should be reasonably quick) so it's still gonna be quite some time before I have anything here.

c/4 odd to population 61 I already extrapolated to take 5 days for worst phase (of four) and need that same fanciest computer. I'm not as sure about the other three phases but I assume they'll be between 0 and 5 days each. So probably a few weeks additional for this (which is queued to run on fancy computer).

I ran some preliminary small searches on a weaker computer to try to get vague idea for the other proposed symmetric geometries:

2c/5 odd to population 57 I believe is in range (estimated ~68G memory and ~15 days for worst of five phases (on weaker computer)), but it's also gonna need the fanciest computer (and is also now queued).

2c/5 even to population 70 is projected to be ~400 GB so it's a little beyond my reach for now. Something something swap file or next time I rent an EC2 box.

c/5 odd to population 58 and c/6 even to population 28 are both projected to use in the hundreds of TB of memory and while the extrapolations are somewhat far and so maybe it's lower, I think these are still probably entirely out of reach for current techniques.

[amling]

I'm about to head out of town again for about two weeks. In the meantime the worst phase (of two) for c/2 asymmetric to pop 127 is running on my fanciest computer (and already has been for two weeks!). Examining time/memory patterns for smaller runs more closely and trying to estimate from the log so far I think it probably has another two weeks (and based on other extrapolation, the easier of the two phases should be reasonably quick) so it's still gonna be quite some time before I have anything here.

Both phases of c/2 asymmetric to pop 127 have finally finished. The harder phase finished in ~34 days, reaching ~77 GB memory. The easier phase finished in ~5 days, reaching ~36 GB memory. Nearly all of that time was spent in the ugly single-threaded hacks specific to the min-pop project which generate the ships after each row. I had tried in the middle to produce a better performing (parallel) version but it was hard to benchmark as less gigantic searches don't spend as much proportional time in it and ultimately I gave up to just wait it out.

The final counts per-population and cumulative up-to-population were:

Code: Select all

pop   ct        cumulative_ct
---   -------   -------------
64    1         1            
65    1         2            
66    2         4            
67    1         5            
68    4         9            
69    2         11           
70    9         20           
71    6         26           
72    13        39           
73    14        53           
74    17        70           
75    27        97           
76    20        117          
77    36        153          
78    47        200          
79    56        256          
80    62        318          
81    97        415          
82    103       518          
83    157       675          
84    171       846          
85    244       1090         
86    306       1396         
87    345       1741         
88    516       2257         
89    467       2724         
90    879       3603         
91    749       4352         
92    1334      5686         
93    1202      6888         
94    1816      8704         
95    1943      10647        
96    2511      13158        
97    3046      16204        
98    3835      20039        
99    4657      24696        
100   5726      30422        
101   6961      37383        
102   8576      45959        
103   10441     56400        
104   13116     69516        
105   16086     85602        
106   19755     105357       
107   24958     130315       
108   29547     159862       
109   37214     197076       
110   44477     241553       
111   55371     296924       
112   66544     363468       
113   82723     446191       
114   99474     545665       
115   123749    669414       
116   148721    818135       
117   184427    1002562      
118   221313    1223875      
119   273406    1497281      
120   331180    1828461      
121   408743    2237204      
122   497303    2734507      
123   615118    3349625      
124   750032    4099657      
125   917054    5016711      
126   1127615   6144326      
127   1370036   7514362      

c/4 odd to population 61 I already extrapolated to take 5 days for worst phase (of four) and need that same fanciest computer. I'm not as sure about the other three phases but I assume they'll be between 0 and 5 days each. So probably a few weeks additional for this (which is queued to run on fancy computer).

2c/5 odd to population 57 I believe is in range (estimated ~68G memory and ~15 days for worst of five phases (on weaker computer)), but it's also gonna need the fanciest computer (and is also now queued).

I may postpone these other min pop searches (c/4 odd to pop 61 and 2c/5 odd to pop 57) a bit while I burn down some of the giant queue of search projects waiting that has shown up over the last month.

[HartmutHolzwart]

Great!

I would be interested in the actual ships found (say up to population count 79), just to see whether there are any surprises. Are they available in a Golly-readable format?

[amling]

Great!

I would be interested in the actual ships found (say up to population count 79), just to see whether there are any surprises. Are they available in a Golly-readable format?

The very first post on the thread has (the differences with jslife-moving) up to pop 80 in `code` blocks, one per population. After that up to pop 98 is somewhere in the middle in an awful format which is approx what LLSSS outputs. After that I did not save ships as there were so very many.