5 ms·

Of all the natural numbers in N, how did it turn out that the last two were so small: 41 and 19? I’d have guessed that maybe some huge number would have been th

by pohl 3y ago

Of all the natural numbers in N, how did it turn out that the last two were so small: 41 and 19? I’d have guessed that maybe some huge number would have been the most difficult.

DemocracyFTW2 3y ago
After years of watching numberphile on Youtube, my guess would be that there's a cutoff number n0 for which can be inductively shown that if n0 is a period then n0+1 is also a period; that would then eliminate almost all natural numbers from the search. Such a proof might perhaps use combining periodic patterns to obtain longer periods. It seems to be difficult to construct a periodic GoL pattern with a given period, so that then would explain why of all numbers two very small ones held out over the decades; this is truly astounding, especially given how incredibly inventive and industrious people have gotten with the Game of Life, simulating entire computers on the canvas.
- AeiumNE 3y ago
  As a fellow numberphile viewer, I accept your authority on the topic, and will probably repeat this guess as fact later.
- mhink 3y ago
  Actually, progress looks like it's been very steady. You're right regarding inductive-style proofs, but the ones for _all_ natural numbers greater than a certain value came surprisingly late. There appear to have been many more oscillators with periods of x + yn (for constant x and y, any natural number n). In 1996 there was a paper showing that it was possible to use a particular family of patterns called "Herschel loops" to create oscillators of any period >= 61. From there, the only missing oscillators were 17, 19, 22, 23, 27, 31, 33, 34, 37, 38, 39, and 41, 49, 51, 53, 57, and 59. There were gradual discoveries of new oscillators over the next several years, then in 2013 there was another pattern discovered which lowered that upper bound to >= 43. At this point, there were only five oscillators missing: 23, 34, 38, 19, and 41. There appear to have been a few years where progress stalled; 23 was found in 2019, and then the last four were found over the course of these past couple years.
Grimblewald 3y ago
would have been great if the last one was 42.
- Dove 3y ago
  42 is special, though, as the longest cycle that requires a its own solution. 43+ can be made as a Snark Loop. https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
  - codeflo 3y ago
    That doesn't make any sense to me. A 6-cycle oscillator next to a 7-cycle oscillator should form a 42-cycle oscillator, or am I missing something?
    - LegionMammal978 3y ago
      This paper is primarily considering nontrivial oscillators, i.e., oscillators in which at least one cell oscillates at the full period, not just some divisor. Still, there are many nontrivial "LCM" oscillators that can be constructed with two lower-period oscillators that just slightly interact. Such an LCM oscillator for p42 ("unix on 44P7.2") could have been constructed for decades; the actual last nontrivial periods to be discovered were p34, p38, p19, and p41.
- readyplayernull 3y ago
  Off by one
- bee_rider 3y ago
  Or if 42 was the only impossible period.
- passion__desire 3y ago
  If you care for 42 to be special, here's video that might be of interest to you. The Answer to the Ultimate Question of Life, the Universe and Everything : https://www.youtube.com/watch?v=ZFxT0sObrYQ https://www.youtube.com/watch?v=ZFxT0sObrYQ
z2trillion 3y ago
From page two of the paper: "Low-period oscillators in Life, roughly p ≤ 15, can be found by playing with patterns by hand or using brute force computer searches. In 1996, David Buckingham demonstrated [6] using his “Herschel conduits” that one can construct oscillators with p ≥ 61 by sending signals around a closed track; the cutoff for systematically constructing oscillators was later improved to p ≥ 43, by Mike Playle’s discovery of the Snark [43]."
- davidgrenier 3y ago
  I was speculating two oscillators with periods p and q could be composed (as long as there was no way for them to interact) to create an oscillator of period p*q/gcd(p,q) but wondering why large primes wouldn't be a problem. I guess this is my answer.
SAI_Peregrinus 3y ago
You can build a Turing Machine in the GoL. Then program a loop. The period needed to execute the loop is rather long (TMs in life aren't very fast), but every period beyond that is trivially just a different TM program. Finding oscillators shorter than the shortest looping TM takes is harder.
- klyrs 3y ago
  This would only get you multiples of your "clock rate."
- kuhewa 3y ago
  You don't want a clunky TM, in GOL terms just a 'signal conduit' with a reasonably short delay on the reflectors so the periodicity can be reduced.
GolDDranks 3y ago
I don't think that's surprising, because surely there are a lot more possible ways to get larger periods than small periods? The amount of possible interactions / mechanisms in play is more limited with small periods. I think that groups of periods over some theshold numbers would also yield more readily to "constructive" approaches where you can "build up" the period using oscillators of a smaller period as components.
- Someone 3y ago
  for example, search for constellations that send gliders back and forth through empty space. If you have one of period p, you can make one of period p + 8n for every n in Ν by moving the guns further away from each other. Find a few guns that take longer to ‘reload’ upon getting ‘hit’. Search on, and hopefully, you can find the 7 other modulos. And it need not be glider guns. It could also be constellations that send a ‘ripple’ through occupied space back and forth. I guess such ones can be made with smaller periods, but may require larger constants than 8 because you typically can’t move them further apart by a single cell. Edit: another comment mentions https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop, a single construct that can be tweaked to have any period ≥ 43.

by pohl 3y ago

Of all the natural numbers in N, how did it turn out that the last two were so small: 41 and 19? I’d have guessed that maybe some huge number would have been the most difficult.

DemocracyFTW2 3y ago

After years of watching numberphile on Youtube, my guess would be that there's a cutoff number n0 for which can be inductively shown that if n0 is a period then n0+1 is also a period; that would then eliminate almost all natural numbers from the search. Such a proof might perhaps use combining periodic patterns to obtain longer periods. It seems to be difficult to construct a periodic GoL pattern with a given period, so that then would explain why of all numbers two very small ones held out over the decades; this is truly astounding, especially given how incredibly inventive and industrious people have gotten with the Game of Life, simulating entire computers on the canvas.

AeiumNE 3y ago
As a fellow numberphile viewer, I accept your authority on the topic, and will probably repeat this guess as fact later.
mhink 3y ago
Actually, progress looks like it's been very steady. You're right regarding inductive-style proofs, but the ones for _all_ natural numbers greater than a certain value came surprisingly late. There appear to have been many more oscillators with periods of x + yn (for constant x and y, any natural number n). In 1996 there was a paper showing that it was possible to use a particular family of patterns called "Herschel loops" to create oscillators of any period >= 61. From there, the only missing oscillators were 17, 19, 22, 23, 27, 31, 33, 34, 37, 38, 39, and 41, 49, 51, 53, 57, and 59. There were gradual discoveries of new oscillators over the next several years, then in 2013 there was another pattern discovered which lowered that upper bound to >= 43. At this point, there were only five oscillators missing: 23, 34, 38, 19, and 41. There appear to have been a few years where progress stalled; 23 was found in 2019, and then the last four were found over the course of these past couple years.

Grimblewald 3y ago

would have been great if the last one was 42.

Dove 3y ago
42 is special, though, as the longest cycle that requires a its own solution. 43+ can be made as a Snark Loop. https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
- codeflo 3y ago
  That doesn't make any sense to me. A 6-cycle oscillator next to a 7-cycle oscillator should form a 42-cycle oscillator, or am I missing something?
  - LegionMammal978 3y ago
    This paper is primarily considering nontrivial oscillators, i.e., oscillators in which at least one cell oscillates at the full period, not just some divisor. Still, there are many nontrivial "LCM" oscillators that can be constructed with two lower-period oscillators that just slightly interact. Such an LCM oscillator for p42 ("unix on 44P7.2") could have been constructed for decades; the actual last nontrivial periods to be discovered were p34, p38, p19, and p41.
readyplayernull 3y ago
Off by one
bee_rider 3y ago
Or if 42 was the only impossible period.
passion__desire 3y ago
If you care for 42 to be special, here's video that might be of interest to you. The Answer to the Ultimate Question of Life, the Universe and Everything : https://www.youtube.com/watch?v=ZFxT0sObrYQ https://www.youtube.com/watch?v=ZFxT0sObrYQ

z2trillion 3y ago

From page two of the paper: "Low-period oscillators in Life, roughly p ≤ 15, can be found by playing with patterns by hand or using brute force computer searches. In 1996, David Buckingham demonstrated [6] using his “Herschel conduits” that one can construct oscillators with p ≥ 61 by sending signals around a closed track; the cutoff for systematically constructing oscillators was later improved to p ≥ 43, by Mike Playle’s discovery of the Snark [43]."

davidgrenier 3y ago
I was speculating two oscillators with periods p and q could be composed (as long as there was no way for them to interact) to create an oscillator of period p*q/gcd(p,q) but wondering why large primes wouldn't be a problem. I guess this is my answer.

SAI_Peregrinus 3y ago

You can build a Turing Machine in the GoL. Then program a loop. The period needed to execute the loop is rather long (TMs in life aren't very fast), but every period beyond that is trivially just a different TM program. Finding oscillators shorter than the shortest looping TM takes is harder.

klyrs 3y ago
This would only get you multiples of your "clock rate."
kuhewa 3y ago
You don't want a clunky TM, in GOL terms just a 'signal conduit' with a reasonably short delay on the reflectors so the periodicity can be reduced.

GolDDranks 3y ago

I don't think that's surprising, because surely there are a lot more possible ways to get larger periods than small periods? The amount of possible interactions / mechanisms in play is more limited with small periods. I think that groups of periods over some theshold numbers would also yield more readily to "constructive" approaches where you can "build up" the period using oscillators of a smaller period as components.

Someone 3y ago
for example, search for constellations that send gliders back and forth through empty space. If you have one of period p, you can make one of period p + 8n for every n in Ν by moving the guns further away from each other. Find a few guns that take longer to ‘reload’ upon getting ‘hit’. Search on, and hopefully, you can find the 7 other modulos. And it need not be glider guns. It could also be constellations that send a ‘ripple’ through occupied space back and forth. I guess such ones can be made with smaller periods, but may require larger constants than 8 because you typically can’t move them further apart by a single cell. Edit: another comment mentions https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop, a single construct that can be tweaked to have any period ≥ 43.