# 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 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

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.

## Notes

1. More generally, all primes of the form n-1k=0(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)*∑n/f-1k=0(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)*∑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. 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. Carson Cheng (April 25, 2023). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums