Note (a) for The Sequence of Primes…Finding primes The sieve of Eratosthenes shown in the picture is an appropriate procedure if one wants to find every prime, but testing whether an individual number is prime can be done much more efficiently, as in PrimeQ[n] in Mathematica, for example by using Fermat's so-called little theorem that Mod[a p - 1 , p]  1 whenever p is prime. The n th prime Prime[n] can also be computed fairly efficiently using ideas from analytic number theory (see the next note ).

Quadratic residue sequences As an outgrowth of ideas related to RSA cryptography it was shown in 1982 by Lenore Blum , Manuel Blum and Michael Shub that the sequence Mod[NestList[Mod[# 2 , m] &, x0, n], 2] discussed on page 975 has the property that if m=p q with p and q primes (congruent to 3 modulo 4) then any systematic regularities detected in the sequence can eventually be used to discover factors of m . … If m is a prime p , then the simple tests JacobiSymbol[x, p]  1 (see page 1081 ) or Mod[x (p - 1)/2 , p]  1 determine whether x is a quadratic residue. But with m = p q , one has to factor m and find p and q in order to carry out similar tests.

Conway considered fraction systems based on rules of the form FSEvolveList[fracs_, init_, t_] := NestList[First[Select[fracs #, IntegerQ, 1]] &, init, t] With the choice fracs = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/ 23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1} starting at 2 the result for Log[2, list] is as shown below, where Rest[Log[2, Select[list, IntegerQ[Log[2, #]] &]]] gives exactly the primes.

Nevertheless, to test whether a number is prime ( PrimeQ ) it is known that only a few more than Log[n] steps suffice.

The first step is to work out so-called prime implicants corresponding to hyperplanes that cannot be contained in higher-dimensional ones. … (For example, in {{0, 0, _}, {0, _, 1}, {_, 0, 0}} the first prime implicant is covered by the others, and can therefore be dropped.) Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF: QM[s_, p_] := First[Sort[Map[p 〚 # 〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]] h[i_, r_, t_] := Flatten[Map[h[Join[i, r 〚 # 〛 ], Drop[r, #], Delete[Drop[t, {}, #], Position[t 〚 All, # 〛 ], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1] h[i_, _, {}] := {i} The number of steps required in this procedure can increase exponentially with the length of p .

Note (d) for The Sequence of Primes…It was shown by Euclid in 300 BC that 2 n - 1 (2 n - 1) is a perfect number whenever 2 n - 1 is prime. … The values of n for the known Mersenne primes 2 n - 1 are shown below. … Various generalizations of perfect numbers have been considered, requiring for example IntegerQ[DivisorSigma[1, n]/n] (pluperfect) or Abs[DivisorSigma[1, n] - 2n] < r (quasiperfect).

This is the simplest polynomial giving Fibonacci[n] , and there are for example no polynomials with 2 variables, up to 4 terms, total degree less than 4, and integer coefficients between -2 and +2, that give any of 2 n , 3 n or Prime[n] . Nevertheless, from the representation for PrimeQ in the note above it has been shown that the positive values of a particular polynomial with 26 variables, 891 terms and total degree 97 are exactly the primes.

Note (d) for The Sequence of Primes…This is nonzero when all prime factors of n of the form 4k + 3 appear with even exponents. … In 1973 it was proved that any even number can be written as the sum of a prime and a number that has at most two prime factors, not necessarily distinct. The number of ways of writing an integer n as a sum of two primes can be calculated explicitly as Length[Select[n - Table[Prime[i], {i, PrimePi[n]}], PrimeQ]] .

Power cellular automata Multiplication by m in base k corresponds to a local cellular automaton operation on digit sequences when every prime that divides m also divides k . … The inverse rule, corresponding to multiplication by 1/m , can be obtained by applying the rule for multiplication by the integer k q /m , then shifting right by q positions.

Maximal period is assured when in addition PrimeQ[2 n - 1] .) … The simplest example uses the rule n  Mod[n 2 , m] It was shown that for m = p q with p and q prime the sequence Mod[n, 2] was in a sense as difficult to predict as the number m is to factor (see page 1090 ). … When m is a prime, this implies that the period can then be as long as (m - 3)/2 .