Prime number: Difference between revisions
Jump to navigation
Jump to search
has page now |
→Medium-period prime-period oscillators: update p29 count, fix HF link, add R hasslers |
||
| 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: Seven known: [[David Hilbert]], [[p23 honey farm hassler]], [[92P23]], [[70P23]], [[55P23]], a [[p23 R-pentomino hassler]], [[112P23]]. | * 23: Seven known: [[David Hilbert]], [[p23 honey farm hassler]], [[92P23]], [[70P23]], [[55P23]], a [[p23 R-pentomino hassler]], [[112P23]]. | ||
* 29: | * 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 /> | ||
* 31: Three known: [[Merzenich's p31]] including p31 hasslers based on it, [[p31 dependent reflector loop]], and a 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 p31 TL hassler.<ref>{{LinkForumThread|p=149198|title=Re: Oscillator Discussion Thread|author=Carson Cheng|date=Aug 05, 2022|format=ref}}</ref> | ||
* 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>{{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>. | ||
Revision as of 05:06, 2 June 2024
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.
- 17: Six known: 54P17.1 and 71P17.1 (variations on the same theme), honey thieves, honey ring, p17 R-pentomino hassler, R2-D2 shifting p5 diamond, and a p17 B-heptomino hassler.[6]
- 19: Two known: cribbage and its stator variants, goban and wick based on it.
- 23: Seven known: David Hilbert, p23 honey farm hassler, 92P23, 70P23, 55P23, a p23 R-pentomino hassler, 112P23.
- 29: Seven known: p29 pre-pulsar shuttle with many variations, p29 traffic-farm hassler, two other p29 honey farm hasslers[7], two p29 R-pentomino hasslers, and a p29 unnamed region hassler.[6]
- 31: Three known: Merzenich's p31 including p31 hasslers based on it, p31 dependent reflector loop, and a p31 TL hassler.[8]
- 37: Six known: Beluchenko's p37, Beluchenko's other p37, 58P37, a p37 traffic light hassler,[9] p37 lumps of muck hassler, p37 wing hassler[10].
- 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 p43 honey farm hassler (88P43),[11] 114P43,[12] LOM + block hassler[13]
- 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, p47 honey farm hassler, and two p47 pi-heptomino hasslers.
- 53: Three known: 94P53 and two p53 pi-heptomino hasslers.
- 59: Four known: 92P59, p59 twirling T-tetsons 2, p59 dependent reflector loop, p59 pi-heptomino hassler.[14]
- 61: Three known: p61 pi-heptomino hassler, a honey farm-based glider gun, and an unnamed object hassler.[13]
- 67: One known: p67 B-heptomino hassler.
- 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; p73 honey farm hassler.
- 79: Five known: three pi-heptomino hasslers, and two p79 glider shuttles.
- 83: Two known: p83 R-pentomino hassler and p83 honey farm hassler.[11]
- 97: One known: p97 honey farm hassler.
- 101: One known: 116P101.
- 107: One known: 86P107.
- 109: One known: p109 R-pentomino hassler.[15]
- 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 p127 R-pentomino hassler.
- 139: One known: p139 century hassler.
- 149: One known: a p149 G-to-LWSS loop.
- 173: One known: a p173 dependent reflector loop.
- 199: One known: p199 R-pentomino hassler.
Notes
- ↑ 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)).)
- ↑ Note that by convention, nested exponentiation is right associative, abc means a(bc), not (ab)c, which could be equivalently written ab*c.
- ↑ 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
- ↑ Prime number at Wikipedia
- ↑ Composite number at Wikipedia
- ↑ Mersenne prime at Wikipedia
- ↑ Fermat prime at Wikipedia
- ↑ Twin prime at Wikipedia
- ↑ 6.0 6.1 Carson Cheng (April 25, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ glider_rider (November 13, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ Carson Cheng (Aug 05, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ Mitchell Riley (Aug 02, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ Nico Brown (April 22, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ 11.0 11.1 glider_rider (November 18, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ glider_rider (April 17, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ 13.0 13.1 hotdogPi (August 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ AlbertArmStain (April 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- ↑ hotdogPi (September 23, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums