Prime number: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
if mentioning p41 stator variants, might as well also for p19 cribbage
 
(42 intermediate revisions by 10 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>∑<sub>k=0</sub><sup>n-1</sup>(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>)*∑<sub>k=0</sub><sup>n/f-1</sup>(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)*∑<sub>k=0</sub><sup>n-1</sup>(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.


* 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: One known: [[204P41]] and its stator variants
* 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: Four known: [[p47 lumps of muck hassler]], an unrelated p47 lumps of muck hassler, [[p47 pre-pulsar shuttle]] and several larger oscillators relying on it, and a [[Honey farm hasslers#p47|p47 honey farm 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: Three known: two [[Pi-heptomino hasslers#p79|pi-heptomino hasslers]], and [[Honey farm hasslers#p79|p79 glider shuttle]].
* 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]].
* 109: One known: [[p109 R-pentomino hassler]].<ref>{{LinkForumThread|p=151301|title=Re: Oscillator Discussion Thread|format=ref}}</ref>
* 103: One known: [[Siffrin's p103]]
* 113: One known: [[86P113]] (aside from the conduit-based [[Nihonium]])
* 107: One known: [[86P107]].
* 127: One known: [[p127 century hassler]].
* 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.
* 127: Two known: [[p127 century hassler]] and [[R-pentomino_hasslers#p127|p127 R-pentomino 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 49: 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