Note (d) for The Sequence of Primes…Results about primes Prime[n] is given approximately by n Log[n] + n Log[Log[n]] . ( Prime[10 9 ] is 22,801,763,489 while the approximation gives 2.38 × 10 10. ) A first approximation to PrimePi[n] is n/Log[n] . … According to the Riemann Hypothesis, the difference between PrimePi[n] and LogIntegral[n] is of order √ n Log[n] . More refined analytical estimates of PrimePi[n] are good enough that they are used by Mathematica to compute Prime[n] for large n .

One way to do this is by using the Gödel number Product[Prime[i]^list 〚 i 〛 , {i, Length[list]}] . … Given p = Array[Prime, Length[list], PrimePi[Max[list]] + 1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive) CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]] yields a number x such that Mod[x, p]  list . Based on this LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[ #1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[ list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]] will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]

Zeta function For real s the Riemann zeta function Zeta[s] is given by Sum[1/n s , {n, ∞ }] or Product[1/(1 - Prime[n] s ), {n, ∞ }] . The zeta function as analytically continued for complex s was studied by Bernhard Riemann in 1859, who showed that PrimePi[n] could be approximated (see page 909 ) up to order √ n by LogIntegral[n] - Sum[LogIntegral[n^r[i]], {i, - ∞ , ∞ }] , where the r[i] are the complex zeros of Zeta[s] . The Riemann Hypothesis then states that all r[i] satisfy Re[r[i]]  1/2 , which implies a certain randomness in the distribution of prime numbers, and a bound of order √ n Log[n] on PrimePi[n] - LogIntegral[n] .

The first step is to work out so-called prime implicants corresponding to hyperplanes that cannot be contained in higher-dimensional ones. Given an original DNF list s , this can be done using PI[s, n] : PI[s_, n_] := Union[Flatten[ FixedPointList[f[Last[#], n] &, {{}, s}] 〚 All, 1 〛 , 1]] g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i]  1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]] f[s_, n_] := With[ {w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[ Select[s, Count[#, 1]  i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest  MatchQ], w}] The minimal DNF then consists of a collection of these prime implicants. … (For example, in {{0, 0, _}, {0, _, 1}, {_, 0, 0}} the first prime implicant is covered by the others, and can therefore be dropped.)

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