Prime number: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
← Older edit
Chris857 (talk | contribs)
Trusted users
2,374 edits
mNo edit summary
 
(30 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{Glossary}}
{{Glossary}}
A '''prime number'''<ref>{{LinkWikipedia|Prime_number|name=Prime number|nobullet=nobullet}}</ref> 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'''<ref>{{LinkWikipedia|Composite_number|name=Composite number|nobullet=nobullet}}</ref>.
A '''prime number'''<ref>{{LinkWikipedia|Prime_number|name=Prime number|nobullet=nobullet}}</ref> 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'''.<ref>{{LinkWikipedia|Composite_number|name=Composite number|nobullet=nobullet}}</ref>


Prime numbers come into play in a number of ways in the [[Game of Life]] and [[OCA]]. Here are some of them:
Prime numbers come into play in a number of ways in the [[Game of Life]] and [[OCA]]. Here are some of them:
Line 12: Line 12:
==Classes of prime numbers==
==Classes of prime numbers==
A Mersenne prime<ref>{{LinkWikipedia|Mersenne_prime|name=Mersenne prime|nobullet=nobullet}}</ref> is a prime number that is one less than a power of two.
A Mersenne prime<ref>{{LinkWikipedia|Mersenne_prime|name=Mersenne prime|nobullet=nobullet}}</ref> is a prime number that is one less than a power of two.
:*All Mersenne primes are of the form <tt>2<sup>p</sup>-1</tt>, where p is a prime number.<ref group="n">More generally, all primes of the form <tt>{{sum|k{{=}}0|n-1|b<sup>k</sup>}}</tt>, that are written as a series of <tt>1</tt>s in base <tt>b</tt>, must have <tt>n</tt> as a prime. If <tt>n</tt> is not, for any <tt>b</tt>, for a number <tt>f</tt> that divides <tt>n</tt>, it can be expressed as <tt>(1+b<sup>f</sup>)*{{sum|k{{=}}0|n/f-1|b<sup>k</sup>}}</tt> (for instance, in any base <tt>b>=2</tt>, when <tt>n=6</tt>, <tt>111111</tt> can be expressed as <tt>1001*111</tt> or <tt>10101*11</tt>).</ref>
:*All Mersenne primes are of the form <tt>2<sup>p</sup>-1</tt>, where p is a prime number.<ref group="n">More generally, all primes of the form <tt>{{sum|k{{=}}0|n-1|b<sup>k</sup>}}</tt>, that are written as a series of <tt>1</tt>s in base <tt>b &ge; 2</tt>, must have <tt>n</tt> as a prime. If <tt>n</tt> is not, for a number <tt>d</tt> that divides <tt>n</tt>, it can be expressed as <tt>{{sum|k{{=}}0|d-1|b<sup>k</sup>}}*{{sum|k{{=}}0|n/d-1|b<sup>d*k</sup>}}</tt> (for instance, when <tt>n=6</tt>, <tt>111111</tt> can be expressed as <tt>1001*111</tt> or <tt>10101*11</tt>). (More generally, all primes of the form <tt>{{sum|k{{=}}0|n-1|x<sup>k</sup>*y<sup>n-1-k</sup>}}</tt> (with coprime <tt>x,y</tt>) must have <tt>n</tt> prime, since they're otherwise equal to <tt>{{sum|k{{=}}0|d-1|x<sup>k</sup>*y<sup>d-1-k</sup>}}*{{sum|k{{=}}0|n/d-1|x<sup>d*k</sup>*y<sup>d*(n/d-1-k)</sup>}}</tt>.)</ref>


A Fermat prime<ref>{{LinkWikipedia|Fermat_prime|name=Fermat prime|nobullet=nobullet}}</ref> is a prime number of the form <tt>2<sup>2<sup>n</sup></sup>+1</tt>,<ref group="n">Note that by convention, nested exponentiation is right associative, <tt>a<sup>b<sup>c</sup></sup></tt> means <tt>a<sup>(b<sup>c</sup>)</sup></tt>, not <tt>(a<sup>b</sup>)<sup><sup>c</sup></sup></tt>, which could be equivalently written <tt>a<sup>b*c</sup></tt>.</ref> where <tt>n</tt> is a nonnegative integer. Only five Fermat primes are known, namely 3, 5, 17, 257, and 65537.
A Fermat prime<ref>{{LinkWikipedia|Fermat_prime|name=Fermat prime|nobullet=nobullet}}</ref> is a prime number of the form <tt>2<sup>2<sup>n</sup></sup>+1</tt>,<ref group="n">Note that by convention, nested exponentiation is right associative, <tt>a<sup>b<sup>c</sup></sup></tt> means <tt>a<sup>(b<sup>c</sup>)</sup></tt>, not <tt>(a<sup>b</sup>)<sup><sup>c</sup></sup></tt>, which could be equivalently written <tt>a<sup>b*c</sup></tt>.</ref> where <tt>n</tt> is a nonnegative integer. Only five Fermat primes are known, namely 3, 5, 17, 257, and 65537.
:*Together with <tt>2</tt>, the Fermat primes are the complete set of prime numbers of the form <tt>2<sup>n</sup>+1</tt> (<tt>n</tt> must be <tt>0</tt> or a power of <tt>2</tt>).<ref group="n">More generally, all numbers of the form <tt>x<sup>n</sup>+y<sup>n</sup></tt> (for integers <tt>x,y>=1</tt> and <tt>n>0</tt>) are prime only if <tt>n</tt> is a power of <tt>2</tt>, because if <tt>n</tt> is odd, <tt>x<sup>n</sup>+y<sup>n</sup>=(x+y)*{{sum|k{{=}}0|n-1|x<sup>k</sup>*(-y)<sup>n-1-k</sup>}}</tt><!--(<tt>∑(map(λ k: x<sup>k</sup>*(-y)<sup>n+~k</sup>,range(n)))</tt> :-)-->. If <tt>n</tt> is even, it can be divided by <tt>2</tt> and <tt>x</tt> and <tt>y</tt> can be replaced with <tt>x<sup>2</sup></tt> and <tt>y<sup>2</sup></tt>. After repeating this process until <tt>n</tt> is odd, <tt>n=1</tt> is the only value such that the summation returns a factor of <tt>1</tt>, which doesn't provide a factorisation. This can be derived using the fact that roots of polynomials in multiple variables are divisible by those of lower degree sharing roots (in this case where <tt>x=-y</tt>), and the expression on the right side of the equation equivalently factorises <tt>x<sup>n</sup>-y<sup>n</sup></tt> in terms of <tt>x+y</tt> when <tt>n</tt> is even (generalising the commonly-known fact that <tt>x<sup>2</sup>-y<sup>2</sup>=(x+y)*(x-y)</tt>).</ref>
:*Together with <tt>2</tt>, the Fermat primes are the complete set of prime numbers of the form <tt>2<sup>n</sup>+1</tt> (<tt>n</tt> must be <tt>0</tt> or a power of <tt>2</tt>).<ref group="n">More generally, all numbers of the form <tt>x<sup>n</sup>+y<sup>n</sup></tt> (for coprime integers <tt>x,y &ge; 1</tt> and <tt>n>0</tt>) are prime only if <tt>n</tt> is a power of <tt>2</tt>, because if <tt>n</tt> is odd, <tt>x<sup>n</sup>+y<sup>n</sup> = (x+y)*{{sum|k{{=}}0|n-1|x<sup>k</sup>*(-y)<sup>n-1-k</sup>}}</tt>. If <tt>n</tt> is even, it can be divided by <tt>2</tt> and <tt>x</tt> and <tt>y</tt> can be replaced with <tt>x<sup>2</sup></tt> and <tt>y<sup>2</sup></tt> (see {{LinkWikipedia|Exponentiation_by_squaring|name=exponentiation by squaring|nobullet=no|nosuffix=no}}). After repeating this until <tt>n</tt> is odd, <tt>n=1</tt> is the only value such that the summation returns a trivial factor of <tt>1</tt> instead of a factorisation.<br />The <tt>n</tt>th Fermat number, <tt>''F''<sub>n</sub></tt>, is defined as <tt>2<sup>2<sup>n</sup></sup>+1</tt> without the primality constraint. Since (by inductively applying the Mersenne factorisation formula) <tt>2<sup>2<sup>n</sup></sup>-1 = {{sum|k{{=}}0|2<sup>n-1</sup>|2<sup>k</sup>}} = {{product|k{{=}}0|n-1|2<sup>2<sup>k</sup></sup>+1}}</tt>, <tt>''F''<sub>n</sub> = {{product|k{{=}}0|n-1|''F''<sub>k</sub>}}+2</tt>, so for <tt>n > k</tt>, <tt>''F''<sub>n</sub> ≡ 2 ([[Modular congruence|mod]] ''F''<sub>k</sub>)</tt>, which makes them coprime (since all Fermat numbers are odd), so the number of Fermat numbers <tt>&le; n</tt>, <tt>⌊log<sub>2</sub>(log<sub>2</sub>(n-1))⌋+1</tt>, is less than the {{LinkWikipedia|prime-counting_function|name=number of primes <tt>&le; n</tt>|nobullet=no|nosuffix=no}}.<br />All divisors of <tt>''F''<sub>n</sub></tt> are of the form <tt>k*2<sup>n</sup>+1</tt>, and for <tt>n &ge; 2</tt>, this can be further refined to <tt>k*2<sup>n+2</sup>+1</tt>.<br /><tt>''F''<sub>n</sub></tt> is composite for all <tt>5 &le; n &le; 32</tt>, and there are believed to be no primes after the initial five from <tt>''F''<sub>0</sub></tt> to <tt>''F''<sub>4</sub></tt>.</ref>


A twin prime<ref>{{LinkWikipedia|Twin_prime|name=Twin prime|nobullet=nobullet}}</ref> 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).
A twin prime<ref>{{LinkWikipedia|Twin_prime|name=Twin prime|nobullet=nobullet}}</ref> 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).
Line 21: Line 21:
==Medium-period prime-period oscillators==
==Medium-period prime-period oscillators==
{{CatRel|Prime-period oscillators}}
{{CatRel|Prime-period oscillators}}
Not counting Snark loops for p43+ and conduit-based oscillators for p59+, there are relatively few known prime-period [[oscillator]]s above 16, although more are starting to be found with symmetric [[CatForce]]. Alternative{{which}} forms of the same oscillator are combined into one.
Not counting Snark loops for p43+ and conduit-based oscillators for p59+, there are relatively few known prime-period [[oscillator]]s above 16, although more are starting to be found with symmetric [[CatForce]]. Alternative{{which}} forms of the same oscillator are combined into one, and supported reactions are also not listed.
See also {{CategoryLink|Prime-period oscillators|style=inline}} for oscillators that have dedicated pages.
See also {{CategoryLink|Prime-period oscillators|style=inline}} for oscillators that have dedicated pages.


* 17: Five known: [[54P17.1]] and [[71P17.1]] (variations on the same theme), [[honey thieves]], [[p17 R-pentomino hassler]], [[R2-D2 shifting p5 diamond]], and a p17 [[B-heptomino hassler]].<ref name="post160840">{{LinkForumThread|format=ref|p=160840|title=Re: Oscillator Discussion Thread|author=Carson Cheng|date=April 25, 2023}}</ref>
* 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]].<ref name="post160840" />
* 19: One known: [[cribbage]] and its stator variants
* 19: Two known: [[cribbage]] and its stator variants, [[goban]] and wick/variants based on it.
* 23: Seven known: [[David Hilbert]], [[p23 honey farm hassler]], [[92P23]], [[70P23]], [[55P23]], 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: Four known: [[p29 pre-pulsar shuttle]] with many variations, [[p29 traffic-farm hassler]], [[Honey farm hasslers#p29|p29 honey farm hassler]]<ref>{{LinkForumThread|format=ref|p=153483|title=Re: Oscillator Discussion Thread}}</ref>, and a p29 unnamed region hassler.<ref name="post160840" />
* 29: Seven known: [[p29 pre-pulsar shuttle]] with many variations and supported reactions, [[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 glider shuttle]], 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 [[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: Seven 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" />, and a [[Dependent reflector#p37|p37 dependent reflector loop]]<ref name="post176338" />.
* 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>{{LinkForumThread|format=ref|p=153770|title=Re: Oscillator Discussion Thread}}</ref>, [[R-pentomino_hasslers#p43|114P43]]<ref>{{LinkForumThread|format=ref|p=160576|title=Re: Oscillator Discussion Thread}}</ref>, LOM + block hassler<ref>https://conwaylife.com/forums/viewtopic.php?p=163279#p163279</ref>
* 43: Five known: [[capped period-43 glider gun]] (80P43), [[p43 pi-heptomino hassler]] (70P43), [[Honey farm hasslers#p43|p43 honey farm hassler]] (88P43),<ref name="post153770" />, [[R-pentomino_hasslers#p43|p43 r-pentomino hassler]] (114P43)<ref name="post160576" />, and a LOM + block hassler <ref name="post163279" />
* 47: Five 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 [[Pi-heptomino hasslers#p47|p47 pi-heptomino hassler]].
* 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 glider shuttle]], [[Pi-heptomino hasslers#p59|p59 pi-heptomino hassler]]<ref>https://conwaylife.com/forums/viewtopic.php?p=160080#p160080</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>https://conwaylife.com/forums/viewtopic.php?p=163279#p163279</ref>.
* 61: Four known: [[p61 pi-heptomino hassler]], a [[Period-61 glider gun (2023)|honey farm-based glider gun]], a pi-heptomino plus block hassler,<ref name="post228470"/> and an unnamed object hassler.<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 glider shuttle]].
* 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: Five known: three [[Pi-heptomino hasslers#p79|pi-heptomino hasslers]], and two [[Dependent reflector#p79|p79 glider shuttles]].
* 79: Seven known: three [[Pi-heptomino hasslers#p79|pi-heptomino hasslers]], one [[Honey farm hasslers#p79|honey farm hassler]], 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>{{LinkForumThread|format=ref|p=153770|title=Re: Oscillator Discussion Thread}}</ref>
* 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]].
* 101: One known: [[116P101]].
* 101: One known: [[116P101]].
* 103: One known: [[Siffrin's p103]]
* 107: One known: [[86P107]].
* 107: One known: [[86P107]].
* 109: One known: [[p109 R-pentomino hassler]].<ref>{{LinkForumThread|p=151301|title=Re: Oscillator Discussion Thread|format=ref}}</ref>
* 109: One known: [[p109 R-pentomino hassler]].<ref name="post151301" />
* 113: One known: [[86P113]] (aside from the conduit-based [[Nihonium]])
* 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]].
* 139: One known: [[Century hasslers#p139|p139 century hassler]].
* 139: One known: [[Century hasslers#p139|p139 century hassler]].
* 149: One known: a [[G-to-LWSS_(2023)|p149 G-to-LWSS loop]].
* 173: One known: a [[Dependent_reflector#p173|p173 dependent reflector loop]].
* 199: One known: [[p199 R-pentomino hassler]].
* 199: One known: [[p199 R-pentomino hassler]].


Line 52: Line 56:
<references group="n" />
<references group="n" />


==References==
== References ==
<references/>
<references>
<ref name="post160840">{{LinkForumThread
|format = ref
|title  = Re: Oscillator Discussion Thread
|p      = 160840
|author = Carson Cheng
|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="post176338">{{LinkForumThread
|format = ref
|title  = Re: Oscillator Discussion Thread
|p      = 176338
|author = Nora Brown
|date  = January 22, 2024
}}</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 = Nora Brown
|date  = November 18, 2022
}}</ref>
<ref name="post151301">{{LinkForumThread
|format = ref
|p      = 151301
|title  = Re: Oscillator Discussion Thread
|author = David Raucci
|date  = September 23, 2022
}}</ref>
<ref name="post160576">{{LinkForumThread
|format  = ref
|p      = 160576
|title  = Re: Oscillator Discussion Thread
|author  = Nora Brown
|date    = April 17, 2023
}}</ref>
<ref name="post160736">{{LinkForumThread
|format  = ref
|p      = 160736
|title  = Re: Oscillator Discussion Thread
|author  = Nora Brown
|date    = April 22, 2023
}}</ref>
<ref name="post153483">{{LinkForumThread
|format  = ref
|p      = 153483
|title  = Re: Oscillator Discussion Thread
|author  = Nora Brown
|date    = November 13, 2022
}}</ref>
<ref name="post149078">{{LinkForumThread
|format  = ref
|p      = 149078
|title  = Re: Oscillator Discussion Thread
|author  = Mitchell Riley
|date    = August 2, 2022
}}</ref>
<ref name="post149198">{{LinkForumThread
|format  = ref
|p      = 149198
|title  = Re: Oscillator Discussion Thread
|author  = Carson Cheng
|date    = August 5, 2022
}}</ref>
<ref name="post228470">{{LinkForumThread
|format  = ref
|p      = 228470
|title  = Re: Oscillator Discussion Thread
|author  = Mitchell Riley
|date    = May 8, 2026
}}</ref>
</references>


[[Category:Mathematical miscellany]]
[[Category:Mathematical miscellany]]
__NOTOC__
__NOTOC__

Latest revision as of 19:23, 22 May 2026

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, and supported reactions are also not listed. 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. ↑ Nora Brown (November 13, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  8. ↑ Carson Cheng (August 5, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  9. ↑ Mitchell Riley (August 2, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  10. ↑ Nora Brown (April 22, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  11. ↑ Nora Brown (January 22, 2024). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  12. ↑ 12.0 12.1 Nora Brown (November 18, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  13. ↑ Nora Brown (April 17, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  14. ↑ 14.0 14.1 David Raucci (August 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  15. ↑ Anivec (April 4, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  16. ↑ Mitchell Riley (May 8, 2026). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  17. ↑ David Raucci (September 23, 2022). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
Retrieved from "https://conwaylife.com/w/index.php?title=Prime_number&oldid=172704"