Prime number: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
updating
m Bring down the gift of <sup>sup</sup> from the heavens (like the great Prometheus before me)
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^p-1</tt>, where p is a prime number.<ref group="n">More generally, all primes of the form <tt>∑_{k=0}^{n-1}(b**k)</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**f)*∑_{k=0}^{n/f-1}(b**k)</tt> (for instance, 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>∑<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>


A Fermat prime<ref>{{LinkWikipedia|Fermat_prime|name=Fermat prime|nobullet=nobullet}}</ref> is a prime number of the form <tt>2^(2^n)+1</tt>, 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^n+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^n+y^n</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^n+y^n=(x+y)*∑_{k=0}^{n-1}((-1)^k*x^(n-1-k)*y^k)</tt>, and if it's even, you can divide it by <tt>2</tt> and square <tt>x</tt> and <tt>y</tt>, repeating until <tt>n</tt> is odd, and <tt>1</tt> is the only odd <tt>n</tt> at which this terminates such that the summation returns <tt>1</tt> (and thus 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^n-y^n</tt> in terms of <tt>x+y</tt> when <tt>n</tt> is even (generalising the commonly-known fact that <tt>x^2-y^2=(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 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>


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).

Revision as of 10:47, 14 July 2023

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.

Notes

  1. ↑ More generally, all primes of the form ∑k=0n-1(bk), that are written as a series of 1s in base b, must have n as a prime. If n is not, for any b, for a number f that divides n, it can be expressed as (1+bf)*∑k=0n/f-1(bk) (for instance, in any base b>=2, when n=6, 111111 can be expressed as 1001*111 or 10101*11).
  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 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)*∑k=0n-1(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. After repeating this process until n is odd, n=1 is the only value such that the summation returns a factor of 1, 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 x=-y), and the expression on the right side of the equation equivalently factorises xn-yn in terms of x+y when n is even (generalising the commonly-known fact that x2-y2=(x+y)*(x-y)).

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. ↑ 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. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  12. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  13. ↑ https://conwaylife.com/forums/viewtopic.php?p=163279#p163279
  14. ↑ https://conwaylife.com/forums/viewtopic.php?p=160080#p160080
  15. ↑ https://conwaylife.com/forums/viewtopic.php?p=163279#p163279
  16. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  17. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums