## Smallest Oscillators Supporting Specific Periods

For discussion of other cellular automata.

### Re: Smallest Oscillators Supporting Specific Periods

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
`x = 5, y = 1, rule = B2cen3eny4jkqrtwz5ejkry6ci7c8/S02i3-ei4ijnrwy5aijq6-n7e8obobo!`

p77, 3 cells
`x = 5, y = 1, rule = B2cin3acijr4aityz5an6ci7e/S02ein3i4c5y6k7e8obobo!`

p109, 3 cells
`x = 5, y = 1, rule = B2cik3-ceq4cijkw5cejy6a7e8/S1e2ae4aeiqw5ey6ack7eobobo!`

p117, 3 cells
`x = 5, y = 1, rule = B2-ak3cikqy4-aikqt5knqy67e8/S12ikn3cen4acekq5acei6cek8obobo!`

p127, 3 cells
`x = 5, y = 1, rule = B2-an3qy4nrtyz5ejqry6c8/S1e2-in3jq4acekntw5ar6aen8obobo!`

p172, 3 cells
`x = 2, y = 3, rule = B2ce3en4acntwyz5ei6ei/S12ek3jn4enr5jr6e2o2\$bo!`

p176, 3 cells
`x = 5, y = 1, rule = B2cin3-iknq4ijkt5ein6-kn8/S1e3-aein4actyz5acnry6k7eobobo!`

p184, 3 cells
`x = 5, y = 1, rule = B2cn3acjy4aceik5ikqry6akn/S01c2-an3einry4eijnqr5aceiy6c7obobo!`

p240, 3 cells
`x = 5, y = 1, rule = B2cei3aeq4ijkryz5jknqy6ai7c/S02ein3-ciny4akty5cknry6i8obobo!`

p248, 3 cells
`x = 2, y = 3, rule = B2cen3kn4aceqry5acjky6en78/S01c2cei3jkry4ceqyz5-ciqr6c7eo\$bo\$o!`

p286, 3 cells
`x = 5, y = 1, rule = B2in3aeiqy4aekrtz5eikqr6ain7c8/S01e2i3eijq4aeik5cj6ac8obobo!`

p320, 3 cells
`x = 2, y = 3, rule = B2ein3-jn4kn5aijkq6-i78/S01c2-cn3ijqy4eikw5cey6ci7eo\$bo\$o!`

p392, 3 cells
`x = 2, y = 3, rule = B2cek3cq4ny5-cnr6c7c/S01e2kn3-aeij4atz5knqr6cin7e2o2\$bo!`
wildmyron

Posts: 874
Joined: August 9th, 2013, 12:45 am

### Re: Smallest Oscillators Supporting Specific Periods

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

p49, 2 cells
`x = 3, y = 1, rule = B2ai3knr4inty5aejy6c7e/S01e2ei3cik4-enwyz5aeijn6aci7eobo!`

p51, 2 cells
`x = 3, y = 1, rule = B2ain3ace4ceijkq5ein6i7e8/S01e2ein3acey4cijk5ci6ac7eobo!`

p53, 2 cells
`x = 3, y = 1, rule = B2-ck3acek4einrt5cy6cei8/S01e2eik3e4acjny5iy6ck7eobo!`

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.
wildmyron

Posts: 874
Joined: August 9th, 2013, 12:45 am

### Re: Smallest Oscillators Supporting Specific Periods

wildmyron wrote:p53, 2 cells
`x = 3, y = 1, rule = B2-ck3acek4einrt5cy6cei8/S01e2eik3e4acjny5iy6ck7eobo!`

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

77topaz

Posts: 859
Joined: January 12th, 2018, 9:19 pm

### Re: Smallest Oscillators Supporting Specific Periods

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?

77topaz

Posts: 859
Joined: January 12th, 2018, 9:19 pm

### Re: Smallest Oscillators Supporting Specific Periods

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?".

Macbi

Posts: 506
Joined: March 29th, 2009, 4:58 am

### Re: Smallest Oscillators Supporting Specific Periods

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
`x = 3, y = 1, rule = B2aci4aintw/S1e2ai4ei5yobo!`

p32, 2 cells
`x = 3, y = 1, rule = B2aci4aintw/S1e2ai4ei5yobo!`

p34, 2 cells
`x = 3, y = 1, rule = B2-kn3e4t5iqy6i/S12i3eqy4cerw5iy6c7e8obo!`

p36, 2 cells
`x = 3, y = 1, rule = B2acei4cr5e7e/S1e2cik3enr4aetobo!`

p62, 2 cells
`x = 3, y = 1, rule = B2-ek3n4ctw/S12i3ace5iobo!`

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

p60, 2 cells
`x = 3, y = 1, rule = B2aei3q4ceinr5j6ci7e/S01e2ek3-acnq4eiknqr5aeiy7eobo!`

p64, 2 cells
`x = 3, y = 1, rule = B2aik3any4eikt5eiy6e8/S01e2-an3knry4-nqtw5iky7eobo!`

p66, 2 cells
`x = 3, y = 1, rule = B2ai3k4cinqty5ijy7e8/S01e2eik3jry4acint5cijny6ac7eobo!`

p68, 2 cells
`x = 3, y = 1, rule = B2ai3aen4ajnrt5eikny6ce7e8/S01e2ei3acery4aceirwy5ceky6cobo!`

Edit: (I couldn't resist)
p70, 2 cells
`x = 3, y = 1, rule = B2ain3acr4eijnwy5-jkny6-cn7e/S01e2-ai3-in4jknty5-qr6-in7e8obo!`

p72, 2 cells
`x = 3, y = 1, rule = B2aei3cjqy4-aet5-q6ace7e8/S01e2ei3aijkr4ackw5acer6ackobo!`

p74, 2 cells
`x = 3, y = 1, rule = B2-ck3aeky4eir5jy8/S01e2eik3en4acnqt5ciny6cek7eobo!`

p76, 2 cells
`x = 3, y = 1, rule = B2aei3enq4eijkq5ceny6ci7e/S01e2eik3cinr4enrt5-jkr6eiobo!`

p78, 2 cells
`x = 3, y = 1, rule = B2aei3aenq4aiktw5ae6cei8/S01e2ein3-ain4aijkn5ry6ciobo!`

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)
`x = 3, y = 1, rule = B2aei3acen4aciy5einy6i/S01e2in3aejy4acejn5ij6ac7eobo!`

p82, 2 cells (20 mins in lls)
`x = 3, y = 1, rule = B2aei3ekqry4jnr5cej6ci7e8/S01e2eik3ejnr4cirt5jy6ce7e8obo!`

If anyone is curious, this is the method I've been using to find these (example for p78, 2 minutes search time):
`\$ 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
`x = 3, y = 1, rule = B2ai3acejq4eky5eijy6ae7e8/S01e2cei3-ciny4-ejqrz5-cejr7e8obo!`

p86, 2 cells
`x = 3, y = 1, rule = B2aei3cekqy4-acrt5-aeij6-n7e8/S01e2ekn3einr4nqrtwy5-eqr6ack7eobo!`

[/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.
wildmyron

Posts: 874
Joined: August 9th, 2013, 12:45 am

### Re: Smallest Oscillators Supporting Specific Periods

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

Majestas32

Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Smallest Oscillators Supporting Specific Periods

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.

Macbi

Posts: 506
Joined: March 29th, 2009, 4:58 am

### Re: Smallest Oscillators Supporting Specific Periods

I mean in the 2 cell phase

Majestas32

Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Smallest Oscillators Supporting Specific Periods

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
wildmyron

Posts: 874
Joined: August 9th, 2013, 12:45 am

### Re: Smallest Oscillators Supporting Specific Periods

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.

77topaz

Posts: 859
Joined: January 12th, 2018, 9:19 pm

### Re: Smallest Oscillators Supporting Specific Periods

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.
Last edited by Macbi on June 1st, 2018, 4:58 am, edited 1 time in total.

Macbi

Posts: 506
Joined: March 29th, 2009, 4:58 am

### Re: Smallest Oscillators Supporting Specific Periods

What about 2 cells 1 cell apart diagonally

With B2en and S01c

Or 2 cells 1 apart knightwise

With b2ak and S0

Majestas32

Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Smallest Oscillators Supporting Specific Periods

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.

Macbi

Posts: 506
Joined: March 29th, 2009, 4:58 am

### Re: Smallest Oscillators Supporting Specific Periods

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?

Majestas32

Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Smallest Oscillators Supporting Specific Periods

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

Majestas32

Posts: 509
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Smallest Oscillators Supporting Specific Periods

`x = 3, y = 3, rule = B3jy/S012cobo2\$bo!`

`x=3, y=3, rule=B3ey/S01bob\$\$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.

wwei23

Posts: 922
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

### Re: Smallest Oscillators Supporting Specific Periods

Macbi wrote:Just skipping the hard ones now. All 2 cells:

p34
`x = 1, y = 3, rule = B2ain3cejkq4-aijtz5-jny6-ai7e/S01e2-ak3-ijqr4aeijnqz5cijry6-ac7eo2\$o!`

p36
`x = 1, y = 3, rule = B2ain3-eiry4ijknrtz5-ay6aek/S01e2-a3-aijn4-acewy5ejqr678o2\$o!`

p38
`x = 1, y = 3, rule = B2ain3-einr4-aent5-kqry6-ci7c/S01e2-a3-iknr4inqt5ceq6-e78o2\$o!`

p40
`x = 1, y = 3, rule = B2ain3acjkq4-acewz5aeiny6ck7e/S01e2-ak3cejqy4ijqtwz5aenr6ci8o2\$o!`

p42
`x = 3, y = 1, rule = B2ain3acjkq4-aey5-y6k7c/S01e2-an3-in4ijnqtwz5-ciny6-ek7e8obo!`

I guess even periods are easier because they can just rotate 90 degrees after half the period.

EDIT: Now that I've exhausted the brute-force approach, I stopped to figure a few things out. 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.

EDIT2: This lets me fill in some missing periods:

p31
`x = 3, y = 1, rule = B2ai3-eikr4ijnqwy5acenq6-e7/S01e2ce3cekr4-aknz5-aijk6ce7eobo!`

p33
`x = 3, y = 1, rule = B2ain3cenqr4-aejqt5-cijr6-ce8/S01e2en3-ceij4aijknr5aekqy6-e7c8obo!`

p35
`x = 3, y = 1, rule = B2ai3acqr4-crt5anqr6-n7c/S01e2k3-cein4-cknq5acej6-ak7e8obo!`

p37
`x = 3, y = 1, rule = B2ain3-eir4inqr5-cen6-cn/S01e2-a3ck4eijnyz5-cnqr6aei78obo!`

p41
`x = 3, y = 1, rule = B2-ck3aky4-ejrw5ceir6-cn7/S01e2en3eikry4cekrz5-k6ack7cobo!`

p44
`x = 3, y = 1, rule = B2ai3-einr4iknqty5aikry6ik7/S01e3cejry4-ejkqr5inry6a7cobo!`

p46
`x = 3, y = 1, rule = B2ai3cekry4aejknrz5aejqy6-en7e/S01e2-a3-inqy4-ijntw5-ijn6-in8obo!`

p48
`x = 3, y = 1, rule = B2ain3-eiy4aqrwyz5-cij6cen7e8/S01e2in3-eknq4ijnryz5aceqr6-ceobo!`

p50
`x = 3, y = 1, rule = B2ain3-aijr4cijkw5anqry6-kn7c8/S012ekn3-ejny4aiz5ceqy6-n8obo!`

wwei23

Posts: 922
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

### Re: Smallest Oscillators Supporting Specific Periods

Why are you directly quoting something that is already in this thread? That is completely pointless, and just takes up space.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere

Posts: 758
Joined: July 1st, 2016, 3:58 pm

### Re: Smallest Oscillators Supporting Specific Periods

AforAmpere wrote:Why are you directly quoting something that is already in this thread? That is completely pointless, and just takes up space.

I can’t select the code box on iPhone, so I have to copy it directly from RLE by pressing quote first, and pressing the back button afterwards but I accidentally hit the submit button instead.

wwei23

Posts: 922
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

### Re: Smallest Oscillators Supporting Specific Periods

wwei23 wrote:
AforAmpere wrote:Why are you directly quoting something that is already in this thread? That is completely pointless, and just takes up space.

I can’t select the code box on iPhone, so I have to copy it directly from RLE by pressing quote first, and pressing the back button afterwards but I accidentally hit the submit button instead.

Then why didn't you just delete the accidental post afterwards? (facepalm)

77topaz

Posts: 859
Joined: January 12th, 2018, 9:19 pm

### Re: Smallest Oscillators Supporting Specific Periods

77topaz wrote:
wwei23 wrote:
AforAmpere wrote:Why are you directly quoting something that is already in this thread? That is completely pointless, and just takes up space.

I can’t select the code box on iPhone, so I have to copy it directly from RLE by pressing quote first, and pressing the back button afterwards but I accidentally hit the submit button instead.

Then why didn't you just delete the accidental post afterwards? (facepalm)

I was waiting for a ride in Disney, and the post was made right before I got on. By the time I got off, it was too late.

wwei23

Posts: 922
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

### Re: Smallest Oscillators Supporting Specific Periods

p241, 24 cells:
`x = 11, y = 11, rule = B2in34cij7e8/S1e2ekn34ent6i4bobo\$bo7bo\$5bo\$3bo3bo\$o3bobo3bo\$2bo5bo\$o3bobo3bo\$3bo3bo\$5bo\$bo7bo\$4bobo!`

77topaz

Posts: 859
Joined: January 12th, 2018, 9:19 pm

### Re: Smallest Oscillators Supporting Specific Periods

By the way wwei23, the thread you created tabulating the results is missing the ones from this other thread: viewtopic.php?f=12&t=3020&start=0&hilit=smallest+oscillators+supporting+specific+periods.

Macbi

Posts: 506
Joined: March 29th, 2009, 4:58 am

### Re: Smallest Oscillators Supporting Specific Periods

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:
`x = 3, y = 1, rule = B2aei3e/S01e2ci3e4eobo!`

non-B0 p6:
`x = 3, y = 1, rule = B2aci4c5y6c/S1e2k3q4cobo!`

p7:
`x = 3, y = 1, rule = B2aci4c5y6c/S1e2k3iq4c6iobo!`

p21:
`x = 3, y = 1, rule = B2aci3cq4c5y6c/S1e2k3iqy4ce5y6ain8obo!`

wwei23

Posts: 922
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

PreviousNext