Prime number: Difference between revisions

From LifeWiki
Jump to navigation Jump to search
Add important facts beneath Mersenne and Fermat primes, and notes section regarding additional (less important but interesting) facts (billions must become numerate), also I didn't know about <tt>inline monospacing</tt> (this will be useful for my programming articles I think)
Confocal (talk | contribs)
m →References: notoc
Line 53: Line 53:


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

Revision as of 00:27, 27 April 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 2^p-1, where p is a prime number.[n 1]

A Fermat prime[4] is a prime number of the form 2^(2^n)+1, 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 2^n+1 (n must be 0 or a power of 2).[n 2]

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=0}^{n-1}(b**k), 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+b**f)*∑_{k=0}^{n/f-1}(b**k) (for instance, when n=6, 111111 can be expressed as 1001*111 or 10101*11).
  2. ↑ More generally, all numbers of the form x^n+y^n (for integers x,y>=1 and n>0) are prime only if n is a power of 2, because if n is odd, x^n+y^n=(x+y)*∑_{k=0}^{n-1}((-1)^k*x^(n-1-k)*y^k), and if it's even, you can divide it by 2 and square x and y, repeating until n is odd, and 1 is the only odd n at which this terminates such that the summation returns 1 (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 x=-y), and the expression on the right side of the equation equivalently factorises x^n-y^n in terms of x+y when n is even (generalising the commonly-known fact that x^2-y^2=(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=160080#p160080
  14. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  15. ↑ Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums