# Prime number

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`, where p is a prime number.^{p}-1^{[n 1]}

- All Mersenne primes are of the form

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

- Together with

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: 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.
^{[6]} - 19: One known: cribbage and its stator variants
- 23: Seven known: David Hilbert, p23 honey farm hassler, 92P23, 70P23, 55P23, a p23 R-pentomino hassler, 112P23.
- 29: Four known: p29 pre-pulsar shuttle with many variations, p29 traffic-farm hassler, p29 honey farm hassler
^{[7]}, and a p29 unnamed region hassler.^{[6]} - 31: Three known: Merzenich's p31 including p31 hasslers based on it, p31 glider shuttle, 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: 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, p47 honey farm hassler, and p47 pi-heptomino hassler.
- 53: Three known: 94P53 and two p53 pi-heptomino hasslers.
- 59: Four known: 92P59, p59 twirling T-tetsons 2, p59 glider shuttle, p59 pi-heptomino hassler
^{[14]}. - 61: Three known: p61 pi-heptomino hassler, a honey farm-based glider gun, and an unnamed object hassler
^{[15]}. - 67: One known: p67 B-heptomino hassler.
- 71: Two known: p71 honey farm hassler, p71 glider shuttle.
- 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.
^{[16]} - 101: One known: 116P101.
- 107: One known: 86P107.
- 109: One known: p109 R-pentomino hassler.
^{[17]} - 113: One known: 86P113 (aside from the conduit-based Nihonium)
- 127: Two known: p127 century hassler and p127 R-pentomino hassler.
- 139: One known: p139 century hassler.
- 199: One known: p199 R-pentomino hassler.

## Notes

- ↑ More generally, all primes of the form
`∑n-1k=0(b`, that are written as a series of^{k})`1`s 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`(for instance, in any base^{f})*∑n/f-1k=0(b^{k})`b>=2`, when`n=6`,`111111`can be expressed as`1001*111`or`10101*11`). - ↑ Note that by convention, nested exponentiation is right associative,
`a`means^{bc}`a`, not^{(bc)}`(a`, which could be equivalently written^{b})^{c}`a`.^{b*c} - ↑ More generally, all numbers of the form
`x`(for integers^{n}+y^{n}`x,y>=1`and`n>0`) are prime only if`n`is a power of`2`, because if`n`is odd,`x`. If^{n}+y^{n}=(x+y)*∑n-1k=0(x^{k}*(-y)^{n-1-k})`n`is even, it can be divided by`2`and`x`and`y`can be replaced with`x`and^{2}`y`. After repeating this process until^{2}`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`x`in terms of^{n}-y^{n}`x+y`when`n`is even (generalising the commonly-known fact that`x`).^{2}-y^{2}=(x+y)*(x-y)

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