ConwayLife.com • Smallest Oscillators Supporting Specific Periods - Page 2

Page 2 of 8

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 18th, 2018, 11:55 pm

by wildmyron

I ran my 3 cell oscillator search for a while longer, and as a result here are a few more 3 cell oscillators which fill in a few of the odd period gaps up to p128 and a few higher even periods. No p59 showed up, so I thought I'd give LLS a go. The search I ran specified the initial phase of the oscillator and D4+ symmetry, without which I don't believe the search would have been viable.

Edit: It's worth noting that the bounding box for the p59 search with LLS was probably larger than necessary, so an equivalent search with smaller bbox would probably have been faster, but I wanted to be sure that the search would be successful. [/edit]

I believe only the following periods up to p100 are missing small oscillators (in this thread):
p71 (8 cells), p75 (29 cells), p81, p83, p85, p91 (14 cells), p93, p95, p97 (24 cells), and p99 (56 cells).

p59, 3 cells, found with LLS after 4.5h of search time

Code: Select all

x = 5, y = 1, rule = B2cen3eny4jkqrtwz5ejkry6ci7c8/S02i3-ei4ijnrwy5aijq6-n7e8
obobo!

p77, 3 cells

Code: Select all

x = 5, y = 1, rule = B2cin3acijr4aityz5an6ci7e/S02ein3i4c5y6k7e8
obobo!

p109, 3 cells

Code: Select all

x = 5, y = 1, rule = B2cik3-ceq4cijkw5cejy6a7e8/S1e2ae4aeiqw5ey6ack7e
obobo!

p117, 3 cells

Code: Select all

x = 5, y = 1, rule = B2-ak3cikqy4-aikqt5knqy67e8/S12ikn3cen4acekq5acei6cek8
obobo!

p127, 3 cells

Code: Select all

x = 5, y = 1, rule = B2-an3qy4nrtyz5ejqry6c8/S1e2-in3jq4acekntw5ar6aen8
obobo!

p172, 3 cells

Code: Select all

x = 2, y = 3, rule = B2ce3en4acntwyz5ei6ei/S12ek3jn4enr5jr6e
2o2$bo!

p176, 3 cells

Code: Select all

x = 5, y = 1, rule = B2cin3-iknq4ijkt5ein6-kn8/S1e3-aein4actyz5acnry6k7e
obobo!

p184, 3 cells

Code: Select all

x = 5, y = 1, rule = B2cn3acjy4aceik5ikqry6akn/S01c2-an3einry4eijnqr5aceiy6c7
obobo!

p240, 3 cells

Code: Select all

x = 5, y = 1, rule = B2cei3aeq4ijkryz5jknqy6ai7c/S02ein3-ciny4akty5cknry6i8
obobo!

p248, 3 cells

Code: Select all

x = 2, y = 3, rule = B2cen3kn4aceqry5acjky6en78/S01c2cei3jkry4ceqyz5-ciqr6c7e
o$bo$o!

p286, 3 cells

Code: Select all

x = 5, y = 1, rule = B2in3aeiqy4aekrtz5eikqr6ain7c8/S01e2i3eijq4aeik5cj6ac8
obobo!

p320, 3 cells

Code: Select all

x = 2, y = 3, rule = B2ein3-jn4kn5aijkq6-i78/S01c2-cn3ijqy4eikw5cey6ci7e
o$bo$o!

p392, 3 cells

Code: Select all

x = 2, y = 3, rule = B2cek3cq4ny5-cnr6c7c/S01e2kn3-aeij4atz5knqr6cin7e
2o2$bo!

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 19th, 2018, 10:13 pm

by wildmyron

Pushing the envelope a bit further with high, odd period oscillators having 2 cells in minimum phase (using LLS again):

p49, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ai3knr4inty5aejy6c7e/S01e2ei3cik4-enwyz5aeijn6aci7e
obo!

p51, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ain3ace4ceijkq5ein6i7e8/S01e2ein3acey4cijk5ci6ac7e
obo!

p53, 2 cells

Code: Select all

x = 3, y = 1, rule = B2-ck3acek4einrt5cy6cei8/S01e2eik3e4acjny5iy6ck7e
obo!

The non-prime periods were found with a custom search forcing non-subperiodic solutions. I'm looking forward to the improvements to LLS providing this functionality. However, I think I'll leave this project as it is for now.

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 19th, 2018, 10:22 pm

by 77topaz

wildmyron wrote:p53, 2 cells
Code: Select all
x = 3, y = 1, rule = B2-ck3acek4einrt5cy6cei8/S01e2eik3e4acjny5iy6ck7e
obo!

Hmm... it's interesting how this oscillator behaves somewhat like a failed replicator (look at generation 9).

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 21st, 2018, 11:54 pm

by 77topaz

A slight diversion, but one related to the purpose of this thread:

There are only finitely many range-1 isotropic non-totalistic Life-like cellular automata. A very large number, but a finite one.
There are only finitely many arrangements of two live cells in a single rule that could be an oscillator, as two live cells separated by more than one dead cell cannot interact with each other without B0 or B1; with B1, all patterns grow infinitely and so cannot oscillate, and B0 oscillators are excluded from this project because of how different B0 rules are from others.
Therefore, there are only finitely many unique two-cell oscillators in range-1 rules without B0.
Therefore, there must exist some finite number so that all two-cell oscillators in range-1 rules without B0 have periods equal to or less than that number.

I wonder, what is that maximum period? Is that even calculable with current technology?

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 22nd, 2018, 5:02 am

by Macbi

In fact I already figured out a bit about the positioning of the cells and the rules.

If you want a 2-cell high-period oscillator the two cells have to be one cell apart orthogonally. Then you have to have B2i, S0, B2a, S1e. You can't have B0, B1c, B1e, B2c, B3i.

So to search for 2 cell oscillators you can set LLS up with two cells one cell apart in some size of bounding box and enforce the rules I mentioned.
Then all LLS is doing is searching through all remaining rules to find an oscillator of the given period.

77topaz wrote:I wonder, what is that maximum period? Is that even calculable with current technology?

More possible to answer would be "What's the minimum period not achievable?".

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 3:39 am

by wildmyron

Macbi wrote:In fact I already figured out a bit about the positioning of the cells and the rules.
If you want a 2-cell high-period oscillator the two cells have to be one cell apart orthogonally. Then you have to have B2i, S0, B2a, S1e. You can't have B0, B1c, B1e, B2c, B3i.
So to search for 2 cell oscillators you can set LLS up with two cells one cell apart in some size of bounding box and enforce the rules I mentioned.
Then all LLS is doing is searching through all remaining rules to find an oscillator of the given period.

This is pretty much the method (and rule restrictions I followed), although I also enforced D4+ symmetry and forgot about the -c option (instead I enforced the center cell on in relevant generations). There is however an alternate set of rule restrictions: here are a few high period oscillators without S0 and with B2c in their rule specification:

p30, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aci4aintw/S1e2ai4ei5y
obo!

p32, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aci4aintw/S1e2ai4ei5y
obo!

p34, 2 cells

Code: Select all

x = 3, y = 1, rule = B2-kn3e4t5iqy6i/S12i3eqy4cerw5iy6c7e8
obo!

p36, 2 cells

Code: Select all

x = 3, y = 1, rule = B2acei4cr5e7e/S1e2cik3enr4aet
obo!

p62, 2 cells

Code: Select all

x = 3, y = 1, rule = B2-ek3n4ctw/S12i3ace5i
obo!

Here are a few more reductions down to 2 cells for even periods:

p60, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aei3q4ceinr5j6ci7e/S01e2ek3-acnq4eiknqr5aeiy7e
obo!

p64, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aik3any4eikt5eiy6e8/S01e2-an3knry4-nqtw5iky7e
obo!

p66, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ai3k4cinqty5ijy7e8/S01e2eik3jry4acint5cijny6ac7e
obo!

p68, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ai3aen4ajnrt5eikny6ce7e8/S01e2ei3acery4aceirwy5ceky6c
obo!

Edit: (I couldn't resist)
p70, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ain3acr4eijnwy5-jkny6-cn7e/S01e2-ai3-in4jknty5-qr6-in7e8
obo!

p72, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aei3cjqy4-aet5-q6ace7e8/S01e2ei3aijkr4ackw5acer6ack
obo!

p74, 2 cells

Code: Select all

x = 3, y = 1, rule = B2-ck3aeky4eir5jy8/S01e2eik3en4acnqt5ciny6cek7e
obo!

p76, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aei3enq4eijkq5ceny6ci7e/S01e2eik3cinr4enrt5-jkr6ei
obo!

p78, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aei3aenq4aiktw5ae6cei8/S01e2ein3-ain4aijkn5ry6ci
obo!

Most of those searches only took a few minutes. For some reason p80 is taking much longer.
[/edit]

Edit 2:
p80, 2 cells (30 mins in lls)

Code: Select all

x = 3, y = 1, rule = B2aei3acen4aciy5einy6i/S01e2in3aejy4acejn5ij6ac7e
obo!

p82, 2 cells (20 mins in lls)

Code: Select all

x = 3, y = 1, rule = B2aei3ekqry4jnr5cej6ci7e8/S01e2eik3ejnr4cirt5jy6ce7e8
obo!

If anyone is curious, this is the method I've been using to find these (example for p78, 2 minutes search time):

Code: Select all

$ python make_lls_grid.py -p 39 -m 90 -f 3 3 5 7 > osc.txt
$ python lls osc.txt -r pB2ai3-i45678/S012345678 --force_at_most 2 -s "D4+" -m -c 0 2 -c 0 6

[/edit]

Edit 3:
p84, 2 cells

Code: Select all

x = 3, y = 1, rule = B2ai3acejq4eky5eijy6ae7e8/S01e2cei3-ciny4-ejqrz5-cejr7e8
obo!

p86, 2 cells

Code: Select all

x = 3, y = 1, rule = B2aei3cekqy4-acrt5-aeij6-n7e8/S01e2ekn3einr4nqrtwy5-eqr6ack7e
obo!

[/edit]

Macbi wrote:
77topaz wrote:I wonder, what is that maximum period? Is that even calculable with current technology?
More possible to answer would be "What's the minimum period not achievable?".

Even that might be problematic, because there's no easy way to define a limit on what the bounding box of the oscillator is or what its maximum population is. There's probably a way, but I can't see how you rule out an extremely high period oscillator which grows and grows and then suddenly collapses back down to 2 cells. I suspect though that any upper bound would be astronomically larger than the true value.

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 9:39 am

by Majestas32

Well without b0/b1c/b1e a 2 cell osc has to be within a bounding box of 3x3...

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 10:11 am

by Macbi

wildmyron wrote:There is however an alternate set of rule restrictions: here are a few high period oscillators without S0 and with B2c in their rule specification:

Oh! I missed that possibility.

Majestas32 wrote:Well without b0/b1c/b1e a 2 cell osc has to be within a bounding box of 3x3...

That's not true either, you can escape with 2a.

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 11:12 am

by Majestas32

I mean in the 2 cell phase

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 11:38 am

by wildmyron

Macbi wrote:
Majestas32 wrote:Well without b0/b1c/b1e a 2 cell osc has to be within a bounding box of 3x3...
That's not true either, you can escape with 2a.

Majestas32 wrote:I mean in the 2 cell phase

True, the minimum population phase is within a 3x3 bounding box, but the upper bound on an oscillator's period is determined by the total number of cells which are active at any time

Re: Smallest Oscillators Supporting Specific Periods

Posted: February 23rd, 2018, 4:34 pm

by 77topaz

Majestas32 wrote:Well without b0/b1c/b1e a 2 cell osc has to be within a bounding box of 3x3...

That's already what I said earlier. But, I think what wildmyron meant is that LLS requires the bounding box of the entire evolution of the oscillator, which could be significantly larger than 3x3 at high periods.

Re: Smallest Oscillators Supporting Specific Periods

Posted: March 9th, 2018, 10:39 am

by Macbi

I don't have time to write the code right now (anyone else is welcome to) but I think it might be possible to enumerate every 2-cell oscillator.

Start with a fixed 100 by 100 grid with two cells one cell apart horizontally in the middle of it (actually use symmetry to only simulate one quadrant). Store a partial rule which starts with B2a turned on, B01ce turned off and all other transitions unknown.

Then repeat the following procedure recursively. List all the transitions in the current pattern that aren't yet assigned. For each possible assignment to them evolve the pattern one generation. Then if the pattern has returned to its original state (or its rotation) you've found an oscillator. The current partial rule tells you exactly all the rules it works in. Save the rule for this oscillator and backtrack. If instead you reach a pattern that you've seen in a previous generation (or it's rotation) you have some other oscillator and you should backtrack immediately. You should also backtrack immediately if you create a pattern with two adjacent cells on the outer edge. Because of 2a it will explode.

I believe that this will quite quickly produce a list of all possible 2-cell oscillators. It's searching through the whole 2^transitions sized rulespace, but it can eliminate multiple rules at a time because it keeps track for each evolution of only the transitions needed for that evolution to work.

Re: Smallest Oscillators Supporting Specific Periods

Posted: March 9th, 2018, 11:06 am

by Majestas32

What about 2 cells 1 cell apart diagonally

With B2en and S01c

Or 2 cells 1 apart knightwise

With b2ak and S0

Re: Smallest Oscillators Supporting Specific Periods

Posted: March 9th, 2018, 11:10 am

by Macbi

I meant to add that all other oscillators can be enumerated by hand.

Majestas32 wrote:What about 2 cells 1 cell apart diagonally

With B2en and S0

I think it's true that such a pattern can't escape its bounding box without acquiring D8 symmetry which it can't then get rid of. So it's easy to enumerate all such oscillators by hand.

Re: Smallest Oscillators Supporting Specific Periods

Posted: March 9th, 2018, 11:18 am

by Majestas32

Hmmm, yah.

But knightwise maybe? Or since there can't be 3 cells in a row without symmetry then it can't expand either even with b2ak?

Re: Smallest Oscillators Supporting Specific Periods

Posted: March 9th, 2018, 11:21 am

by Majestas32

This means without b2a 2 cells can only be p1, p2, p3, p4, p6, or p8.

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 1st, 2018, 1:36 pm

by wwei23

BlinkerSpawn wrote:3-cell p3:
Code: Select all
x = 3, y = 3, rule = B3jy/S012c
obo2$bo!

Code: Select all

x=3, y=3, rule=B3ey/S01
bob$$obo!

Edit:
I will tabulate everything here:
viewtopic.php?f=12&t=3352&p=58739#p58739
Edit:
A smaller P3 is known. We need a 2 cell P5, and a P7.

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 2nd, 2018, 4:14 am

by 77topaz

p241, 24 cells:

Code: Select all

x = 11, y = 11, rule = B2in34cij7e8/S1e2ekn34ent6i
4bobo$bo7bo$5bo$3bo3bo$o3bobo3bo$2bo5bo$o3bobo3bo$3bo3bo$5bo$bo7bo$4bo
bo!

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 2nd, 2018, 1:41 pm

by Macbi

By the way wwei23, the thread you created tabulating the results is missing the ones from this other thread: http://conwaylife.com/forums/viewtopic. ... ic+periods.

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 2nd, 2018, 1:47 pm

by wwei23

Macbi wrote:By the way wwei23, the thread you created tabulating the results is missing the ones from this other thread: http://conwaylife.com/forums/viewtopic. ... ic+periods.

I do not allow B0 in my tabulations anymore. It causes an infinite average population, which I cannot accept.
Edit:
[Saka]
ABHPZTA HAS DONE IT AGAIN PEOPLEEEEEEÈÉÊËĒĖĘEE!!!!!!!!
[/Saka]

AbhpzTa wrote:p5:
Code: Select all
x = 3, y = 1, rule = B2aei3e/S01e2ci3e4e
obo!
non-B0 p6:
Code: Select all
x = 3, y = 1, rule = B2aci4c5y6c/S1e2k3q4c
obo!
p7:
Code: Select all
x = 3, y = 1, rule = B2aci4c5y6c/S1e2k3iq4c6i
obo!
p21:
Code: Select all
x = 3, y = 1, rule = B2aci3cq4c5y6c/S1e2k3iqy4ce5y6ain8
obo!

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 2nd, 2018, 2:44 pm

by Naszvadi

Macbi wrote:All 2 cell populations:

...
p8
Code: Select all
x = 3, y = 3, rule = B2en3cejq4cjkt5jkny6i8/S01c2in3-knr4acknqry5qry6aik
2bo2$o!
...

You probably forgot this 2bit p8: ../forums/viewtopic.php?f=12&t=3020#p53012

Code: Select all

#C Moore neighbourhood still violates symmetry
x = 2, y = 4, rule = B02/S1V
o3$bo!

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 2nd, 2018, 2:51 pm

by wwei23

Naszvadi wrote:
Macbi wrote:All 2 cell populations:

...
p8
Code: Select all
x = 3, y = 3, rule = B2en3cejq4cjkt5jkny6i8/S01c2in3-knr4acknqry5qry6aik
2bo2$o!
...
You probably forgot this 2bit p8: ../forums/viewtopic.php?f=12&t=3020#p53012
Code: Select all
#C Moore neighbourhood still violates symmetry
x = 2, y = 4, rule = B02/S1V
o3$bo!

I don’t allow B0 in my tabulations.

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 3rd, 2018, 12:19 pm

by Majestas32

:facepalm:

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 3rd, 2018, 12:48 pm

by wwei23

We have a P55, but not a 2 cell one.
On the tabulations. Red means bad, like a 3-cell oscillator, or a period without an oscillator.

Re: Smallest Oscillators Supporting Specific Periods

Posted: April 20th, 2018, 8:16 am

by 2718281828

Some oscillators, from snowflakes, with cells 19, 14, 15, 16:

Code: Select all

x = 42, y = 61, rule = B2ci3ai4c8/S02ae3eijkq4iz5ar6i7e
3$11bo$9bo$4bo$22b2o6bo4b2o$7bo2bo11bo12bo$22b2o6bo6bo$4bo$9bo$11bo7$
11bo16bo2$4bo30bo2$5bobo4bo14bo4bobo2$4bo30bo2$11bo16bo7$11bo15bo$29bo
$4bo29bo2$5bobo4bo15bo2bo2$4bo29bo$29bo$11bo15bo5$29bo$11bo15bo$27b2o$
4bo2$5bobo4bo$30bo$4bo$27b2o$11bo15bo$29bo!

I know, the populations are quite high, but they can cover all large integers (esp. all > 100) by shifting one part (either left or right), so we have
for
4N: 19 cells
4N+1: 14 cells
4N+2: 15 cells
4N+3: 16 cells
I think this is not optimal but a start for large period oscillators.

EDIT1:
4N: 7 cells

Code: Select all

x = 9, y = 13, rule = B2ek3cei4acjr5c8/S02ack3kn4aen
5bo2$3bo$o3bo$3bo5$8bo3$3bo!