Prime number: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 27: Line 27:
* 19: Two known: [[cribbage]] and its stator variants, [[goban]] and wick based on it.
* 19: Two known: [[cribbage]] and its stator variants, [[goban]] and wick based on it.
* 23: Eight known: [[David Hilbert]], two [[Honey farm hasslers#p23|honey farm hasslers]], [[92P23]], [[70P23]], [[54P23]], a [[p23 R-pentomino hassler]], [[112P23]].
* 23: Eight known: [[David Hilbert]], two [[Honey farm hasslers#p23|honey farm hasslers]], [[92P23]], [[70P23]], [[54P23]], a [[p23 R-pentomino hassler]], [[112P23]].
* 29: Seven known: [[p29 pre-pulsar shuttle]] with many variations, [[p29 traffic-farm hassler]], two other [[Period-29 honey farm hasslers|p29 honey farm hasslers]]<ref>{{LinkForumThread|f=2|t=1437|p=153483|title=Re: Oscillator Discussion Thread|author=glider_rider|date=November 13, 2022|format=ref}}</ref>, two [[R-pentomino hasslers#p29|p29 R-pentomino hasslers]], and a p29 unnamed region hassler.<ref name="post160840" />
* 29: Seven known: [[p29 pre-pulsar shuttle]] with many variations, [[p29 traffic-farm hassler]], two other [[Period-29 honey farm hasslers|p29 honey farm hasslers]]<ref name="post153483" />, two [[R-pentomino hasslers#p29|p29 R-pentomino hasslers]], and a p29 unnamed region hassler.<ref name="post160840" />
* 31: Three known: [[Merzenich's p31]] including p31 hasslers based on it, [[p31 dependent reflector loop]], and a [[traffic light hasslers#p31|p31 TL hassler]].<ref>{{LinkForumThread|p=149198|title=Re: Oscillator Discussion Thread|author=Carson Cheng|date=Aug 05, 2022|format=ref}}</ref>
* 31: Three known: [[Merzenich's p31]] including p31 hasslers based on it, [[p31 dependent reflector loop]], and a [[traffic light hasslers#p31|p31 TL hassler]].<ref name="post149198" />
* 37: Six known: [[Beluchenko's p37]], [[Beluchenko's other p37]], [[58P37]], a [[Traffic light hasslers#p37|p37 traffic light hassler]],<ref>{{LinkForumThread|p=149078|title=Re: Oscillator Discussion Thread|author=Mitchell Riley|date=Aug 02, 2022|format=ref}}</ref> [[p37 lumps of muck hassler]], [[Wing hasslers#p37|p37 wing hassler]]<ref>{{LinkForumThread|format=ref|p=160736|title=Re: Oscillator Discussion Thread|author=Nico Brown|date=April 22, 2023}}</ref>.
* 37: Six known: [[Beluchenko's p37]], [[Beluchenko's other p37]], [[58P37]], a [[Traffic light hasslers#p37|p37 traffic light hassler]],<ref name="post149078" /> [[p37 lumps of muck hassler]], [[Wing hasslers#p37|p37 wing hassler]]<ref name="post160736" />.
* 41: Three known: [[p41 pi-heptomino hassler]], [[204P41]], and [[246P41]].
* 41: Three known: [[p41 pi-heptomino hassler]], [[204P41]], and [[246P41]].
* 43: Five known: [[capped period-43 glider gun]] (80P43), [[p43 pi-heptomino hassler]] (70P43), a [[Honey farm hasslers#p43|p43 honey farm hassler]] (88P43),<ref name=post153770>{{LinkForumThread|f=2|t=1437|p=153770|title=Re: Oscillator Discussion Thread|author=glider_rider|date=November 18, 2022|format=ref}}</ref> [[R-pentomino_hasslers#p43|114P43]],<ref>{{LinkForumThread|f=2|t=1437|p=160576|title=Re: Oscillator Discussion Thread|author=glider_rider|date=April 17, 2023|format=ref}}</ref> LOM + block hassler<ref name=post163279>{{LinkForumThread|f=2|t=1437|p=163279|title=Re: Oscillator Discussion Thread|author=David Raucci|date=August 4, 2023|format=ref}}</ref>
* 43: Five known: [[capped period-43 glider gun]] (80P43), [[p43 pi-heptomino hassler]] (70P43), a [[Honey farm hasslers#p43|p43 honey farm hassler]] (88P43),<ref name="post153770" />, [[R-pentomino_hasslers#p43|p43 r-pentomino hassler]] (114P43), and a  LOM + block hassler <ref name="post163279" />
* 47: Six known: [[p47 lumps of muck hassler]], an unrelated p47 lumps of muck hassler, [[p47 pre-pulsar shuttle]] and several larger oscillators relying on it, [[Honey farm hasslers#p47|p47 honey farm hassler]], and two [[Pi-heptomino hasslers#p47|p47 pi-heptomino hasslers]].
* 47: Six known: [[p47 lumps of muck hassler]], an unrelated p47 lumps of muck hassler, [[p47 pre-pulsar shuttle]] and several larger oscillators relying on it, [[Honey farm hasslers#p47|p47 honey farm hassler]], and two [[Pi-heptomino hasslers#p47|p47 pi-heptomino hasslers]].
* 53: Three known: [[94P53]] and two [[Pi-heptomino hasslers#p53|p53 pi-heptomino hassler]]s.
* 53: Three known: [[94P53]] and two [[Pi-heptomino hasslers#p53|p53 pi-heptomino hassler]]s.
* 59: Four known: [[92P59]], [[p59 twirling T-tetsons 2]], [[p59 dependent reflector loop]], [[Pi-heptomino hasslers#p59|p59 pi-heptomino hassler]].<ref>{{LinkForumThread|f=2|t=1437|p=160080|title=Re: Oscillator Discussion Thread|author=Anivec|date=April 4, 2023|format=ref}}</ref>
* 59: Four known: [[92P59]], [[p59 twirling T-tetsons 2]], [[p59 dependent reflector loop]], [[Pi-heptomino hasslers#p59|p59 pi-heptomino hassler]].<ref name="post160080" />
* 61: Three known: [[p61 pi-heptomino hassler]], a [[Period-61 glider gun (2023)|honey farm-based glider gun]], and an unnamed object hassler.<ref name=post163279 />
* 61: Three known: [[p61 pi-heptomino hassler]], a [[Period-61 glider gun (2023)|honey farm-based glider gun]], and an unnamed object hassler.<ref name="post160576" /> <ref name="post163279" />
* 67: One known: [[p67 B-heptomino hassler]].
* 67: One known: [[p67 B-heptomino hassler]].
* 71: Two known: [[p71 honey farm hassler]], [[p71 dependent reflector loop]].
* 71: Two known: [[p71 honey farm hassler]], [[p71 dependent reflector loop]].
* 73: Two known: [[p73 lumps of muck hassler]] and a larger oscillator supported by four copies of it; [[Honey farm hasslers#p73|p73 honey farm hassler]].
* 73: Two known: [[p73 lumps of muck hassler]] and a larger oscillator supported by four copies of it; [[Honey farm hasslers#p73|p73 honey farm hassler]].
* 79: Six known: three [[Pi-heptomino hasslers#p79|pi-heptomino hasslers]], one [[Long bun hasslers#p79|long bun hassler]], and two [[Dependent reflector#p79|p79 glider shuttles]].
* 79: Six known: three [[Pi-heptomino hasslers#p79|pi-heptomino hasslers]], one [[Long bun hasslers#p79|long bun hassler]], and two [[Dependent reflector#p79|p79 glider shuttles]].
* 83: Two known: [[p83 R-pentomino hassler]] and [[Honey farm hasslers#p83|p83 honey farm hassler]].<ref name=post153770 />
* 83: Two known: [[p83 R-pentomino hassler]] and [[Honey farm hasslers#p83|p83 honey farm hassler]].<ref name="post153770" />
* 97: One known: [[Honey farm hasslers#p97|p97 honey farm hassler]].
* 97: One known: [[Honey farm hasslers#p97|p97 honey farm hassler]].
* 101: One known: [[116P101]].
* 101: One known: [[116P101]].
* 107: One known: [[86P107]].
* 107: One known: [[86P107]].
* 109: One known: [[p109 R-pentomino hassler]].<ref>{{LinkForumThread|f=2|t=1437|p=151301|title=Re: Oscillator Discussion Thread|author=David Raucci|date=September 23, 2022|format=ref}}</ref>
* 109: One known: [[p109 R-pentomino hassler]].<ref name="post151301" />
* 113: One known: [[86P113]] (aside from the conduit-based [[Nihonium]]) and a honey-farm hassler supported by it.
* 113: One known: [[86P113]] (aside from the conduit-based [[Nihonium]]) and a honey-farm hassler supported by it.
* 127: Two known: [[p127 century hassler]] and [[R-pentomino_hasslers#p127|p127 R-pentomino hassler]].
* 127: Two known: [[p127 century hassler]] and [[R-pentomino_hasslers#p127|p127 R-pentomino hassler]].
Line 63: Line 63:
|author = Carson Cheng
|author = Carson Cheng
|date  = April 25, 2023
|date  = April 25, 2023
}}</ref>
<ref name="post160080">{{LinkForumThread
|format = ref
|title  = Re: Oscillator Discussion Thread
|p      = 160080
|author = Anivec
|date  = April 4, 2023
}}</ref>
<ref name="post163279">{{LinkForumThread
|format = ref
|title  = Re: Oscillator Discussion Thread
|p      = 163279
|author=David Raucci
|date=August 4, 2023
}}</ref>
<ref name="post153770">{{LinkForumThread
|format = ref
|p      = 153770
|title  = Re: Oscillator Discussion Thread
|author = Nico Brown
|date  = November 18, 2022
}}</ref>
}}</ref>
<ref name="post151301">{{LinkForumThread
<ref name="post151301">{{LinkForumThread
|format = ref
|format = ref
|t      = 1437
|p      = 151301
|p      = 151301
|title  = Re: Oscillator Discussion Thread
|title  = Re: Oscillator Discussion Thread
|author = David Raucci
|author = David Raucci
|date  = September 23, 2022
|date  = September 23, 2022
|format = ref
}}</ref>
<ref name="post160576">{{LinkForumThread
|format  = ref
|p      = 160576
|title  = Re: Oscillator Discussion Thread
|author  = Nico Brown
|date    = April 17, 2023
}}</ref>
<ref name="post160736">{{LinkForumThread
|format  = ref
|p      = 160736
|title  = Re: Oscillator Discussion Thread
|author  = Nico Brown
|date    = April 22, 2023
}}</ref>
<ref name="post153483">{{LinkForumThread
|format = ref
|p      = 153483
|title  = Re: Oscillator Discussion Thread
|author  = Nico Brown
|date    = November 13, 2022
}}</ref>
<ref name="post149078">{{LinkForumThread
|format  = ref
|p      = 149078
|title  = Re: Oscillator Discussion Thread
|author  = Mitchell Riley
|date    = Aug 02, 2022
}}</ref>
<ref name="post149198">{{LinkForumThread
|format  = ref
|p      = 149198
|title  = Re: Oscillator Discussion Thread
|author  = Carson Cheng
|date    = Aug 05, 2022
}}</ref>
}}</ref>
</references>
</references>

Revision as of 16:41, 10 October 2025

A prime number[1] is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number.[2]

Prime numbers come into play in a number of ways in the Game of Life and OCA. Here are some of them:

  • Large prime oscillators whose periods are very large prime numbers, right up to the largest known prime number
  • Primer, a pattern that produces a stream of lightweight spaceships representing prime numbers
  • Prime calculators using guns whose output stream is filtered by primer to generate twin primes, prime quadruplets, cousin primes, and so forth
  • Fermat prime calculator, a pattern based on primer that calculates Fermat prime numbers
  • Izhora, the largest known cellular automation computer, which can be used to calculate prime numbers

Classes of prime numbers

A Mersenne prime[3] is a prime number that is one less than a power of two.

  • All Mersenne primes are of the form 2p-1, where p is a prime number.[n 1]

A Fermat prime[4] is a prime number of the form 22n+1,[n 2] where n is a nonnegative integer. Only five Fermat primes are known, namely 3, 5, 17, 257, and 65537.

  • Together with 2, the Fermat primes are the complete set of prime numbers of the form 2n+1 (n must be 0 or a power of 2).[n 3]

A twin prime[5] is a prime number that is either 2 less or 2 more than another prime number — for example, either member of the twin prime pair (41, 43).

Medium-period prime-period oscillators

See also category Prime-period oscillators

Not counting Snark loops for p43+ and conduit-based oscillators for p59+, there are relatively few known prime-period oscillators above 16, although more are starting to be found with symmetric CatForce. Alternative[which?] forms of the same oscillator are combined into one. See also category "Prime-period oscillators" for oscillators that have dedicated pages.

Notes

  1. ↑ More generally, all primes of the form ∑n-1k=0(bk), that are written as a series of 1s in base b ≥ 2, must have n as a prime. If n is not, for a number d that divides n, it can be expressed as ∑d-1k=0(bk)*∑n/d-1k=0(bd*k) (for instance, when n=6, 111111 can be expressed as 1001*111 or 10101*11). (More generally, all primes of the form ∑n-1k=0(xk*yn-1-k) (with coprime x,y) must have n prime, since they're otherwise equal to ∑d-1k=0(xk*yd-1-k)*∑n/d-1k=0(xd*k*yd*(n/d-1-k)).)
  2. ↑ Note that by convention, nested exponentiation is right associative, abc means a(bc), not (ab)c, which could be equivalently written ab*c.
  3. ↑ More generally, all numbers of the form xn+yn (for coprime integers x,y ≥ 1 and n>0) are prime only if n is a power of 2, because if n is odd, xn+yn = (x+y)*∑n-1k=0(xk*(-y)n-1-k). If n is even, it can be divided by 2 and x and y can be replaced with x2 and y2 (see exponentiation by squaring ). After repeating this until n is odd, n=1 is the only value such that the summation returns a trivial factor of 1 instead of a factorisation.
    The nth Fermat number, Fn, is defined as 22n+1 without the primality constraint. Since (by inductively applying the Mersenne factorisation formula) 22n-1 = ∑2n-1k=0(2k) = ∏n-1k=0(22k+1), Fn = ∏n-1k=0(Fk)+2, so for n > k, Fn ≡ 2 (mod Fk), which makes them coprime (since all Fermat numbers are odd), so the number of Fermat numbers ≤ n, ⌊log2(log2(n-1))⌋+1, is less than the number of primes ≤ n .
    All divisors of Fn are of the form k*2n+1, and for n ≥ 2, this can be further refined to k*2n+2+1.
    Fn is composite for all 5 ≤ n ≤ 32, and there are believed to be no primes after the initial five from F0 to F4.

References

  1. ↑ Prime number at Wikipedia
  2. ↑ Composite number at Wikipedia
  3. ↑ Mersenne prime at Wikipedia
  4. ↑ Fermat prime at Wikipedia
  5. ↑ Twin prime at Wikipedia
  6. ↑ 6.0 6.1 Carson Cheng (April 25, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  7. ↑ Nico Brown (November 13, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  8. ↑ Carson Cheng (Aug 05, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  9. ↑ Mitchell Riley (Aug 02, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  10. ↑ Nico Brown (April 22, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  11. ↑ 11.0 11.1 Nico Brown (November 18, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  12. ↑ 12.0 12.1 David Raucci (August 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  13. ↑ Anivec (April 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  14. ↑ Nico Brown (April 17, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  15. ↑ David Raucci (September 23, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums