Formula For Primes

In mathematics, it is known that no non-constant polynomial function P(n) exists that evaluates to a prime number for all integers n (or even almost all n). Using algebraic number theory one can make that quite precise. The quadratic polynomial
P(n) = n2 + n + 41
is prime for all non-negative integers less than 40. The primes for n = 0, 1, 2, 3... are 41, 43, 47, 53, 61, 71... The differences between the terms are 2, 4, 6, 8, 10... For n = 40, it produces a square number, 1681, which is equal to 41×41, the smallest composite number for this formula. In fact if 41 divides n it divides P(n) too. The phenomenon is related to the Ulam spiral, which is also implicitly quadratic, and the class number. A set of diophantine equations in 26 variables can be used to obtain primes: A given number k + 2 is prime iff the following system of diophantine equations has a solution in the natural numbers (Riesel, 1994):
0 = wz + h + j - q
0 = (gk + 2g + k + 1)(h + j) + h - z
0 = (16k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2
0 = 2n + p + q + z - e
0 = e^3(e + 2)(a + 1)^2 + 1 - o^2
0 = (a^2 - 1)y^2 + 1 - x^2
0 = 16r^2y^4(a^2 - 1) + 1 - u^2
0 = n + l + v - y
0 = (a^2 - 1)l^2 + 1 - m^2
0 = ai + k + 1 - l - i
0 = ((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2
0 = p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m
0 = q + y(a - p - 1) + s(2ap + 2p - p^2 - 2p - 2) - x
0 = z + pl(a - p) + t(2ap - p^2 - 1) - pm
The following function yields all the primes, and only primes, for non-negative integers n:
f(n) = 2 + (2(n!) \operatorname{mod} (n+1))
This formula is based on Wilson's theorem; the number two is generated many times and all other primes are generated exactly once by this function. (In fact a prime p is generated for n = (p − 1) and 2 otherwise (ie. when n + 1 is composite)) Using the floor function \lfloor x\rfloor (defined to be the largest integer less than or equal to the real number x), one can construct several formulas for the n-th prime. These formulas are also based on Wilson's theorem and have little practical value: the methods mentioned above under "Finding prime numbers" are much more efficient. Define
\pi(m) = \sum_{j=2}^m \frac
{ \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) } or, alternatively,
\pi(m) = \sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor
These definitions are equivalent; π(m) is the number of primes less than or equal to m. The n-th prime number pn can then be written as
p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \pi(m) } \right\rfloor^{1 \over n} \right\rfloor
Another approach does not use factorials and Wilson's theorem, but also heavily employs the floor function (S. M. Ruiz 2000): first define
\pi(k) = k - 1 + \sum_{j=2}^k \left\lfloor {2 \over j} \left(1 + \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor
and then
p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\pi(k) \over n} \right\rfloor\right)

External links

 

<< PreviousWord BrowserNext >>
franois, marquis de barb marbois
play away
fort lauderdale stadium
districts of swaziland
joseph jrme, comte simon
bullpen
genjyo sanzo
yuzhno sakhalinsk airport
advection equation
strontian
vladivostok avia
rakugo
transaero
john rusnak
harry graham (poet)
afterglow (disambiguation)
dalavia far east airways
afterglow (album)
mexican literature
fred f. steen, ii
afterglow (movie)
pyruvate translocase
la vinotinto
republican left (spain)
electrophilic aromatic substitution
republican national convention
endgame (play)
the greens of the madrid community
heptagonal number
mug
oyster card
soda bread
jukka paarma
valdivian temperate rain forests
rivet
cuthred of kent
moshe greenberg
ostracod
adam's mark
kiwi (disambiguation)
fish otolites
empanadas
cycle
ripping