CHAPTER 6

On the history of the problem of searching for finding
generating function of prime numbers "*p*
(n)"

One of the first propounded subjects is that the number of prime numbers is finite or infinite?

Euclid, first time answered this question (more than 2000
years ago) and he proved by a kind of mathematical reasoning (ad absurdum
statement), that the number of prime numbers is infinite. After that time
mathematicians tried to find simple arithmetical formulas, so that with help of
them, it is possible to find only prime numbers even if these formulas couldn’t
present all of prime numbers. Fermat had a famous guess about it (that it
didn’t express as a final conclusion) and that guess is that all of numbers in
form of _{} are prime number. This guess
is correct for *n*=0,1,2,3,4 and called these numbers as "Fermat
prime numbers". In 1732, Euler could decompose *F* (5) to below form:

_{}

Therefore, it is proved that *F* (5) isn’t prime
number. Later Euler could proverb that a lot of these numbers are decomposable
and so composite. It is necessary to mention that so deep methods need to
factorization these numbers in every special case. And because of greatness of
these numbers, it has a lot of unsolvable difficulties. Till now, it couldn’t
be proved that some of other Fermat’s numbers are prime number for_{}.

Another simple and interesting function that generating the number of prime numbers is Euler’s function[1]:

_{}

In fact, _{} generating
prime numbers for n=1, 2, 3, ..., 40 although, for _{} that
isn’t a prime number, because: _{}

Another function that generates prime number for n=1, 2, 3, …, 79 is:

_{}

This generator function of prime numbers also, for n=80, will encounter failure.

"In fact, searching simple expressions that generating just prime numbers is a useless work and even more useless would be trying to find a algebraic formula that generating "all" prime numbers (Richard Courant)."

From Euclid time till now, human has desired a formula
that generating just prime numbers. At first they thought that a polynomial
like F(x) with correct coefficients exists that when an integer number is put
instead of "n", prime number is obtained. But they found out soon
that if _{} be prime then _{}is divisible by "*p*"
for every correct "*k*".

In other word it is proved that such function doesn’t exist
and "*F*" can’t generate just prime numbers. After human became
disappointed from polynomial, he tests non–polynomial formulas.

About this subject, in page "5" of famous book "An entrance on number theory" by Hardy and Wright which printed in 1945, is written:

"Of course must remember that a natural question become
an erroneous question after discussion and verifying …. Is there any general
formula for n^{th} prime number of_{}? ....
Answer of this question is that although it is acceptable as a natural question
but generally it is erroneous then printed in 1968:

Is there any general formula for n^{th} prime number
of"_{}"? … We don’t know such
formula … possibility of such formula, is impossible certainly."

Therefore problems like what were said and especially inquiry
about different forms of numbers for solve the problem of finding prime numbers
formula, were subjects of researches of mathematicians. About this problem, we
can name numbers in "_{}" form that
famous numbers of them are Fermat’s prime numbers _{} and
Mersenne’s prime numbers (M_{p}=2^{p}-1) and they found
favorite. About prime numbers formula, Mills was the first person who presented
an existential formula and his pretty theorem is:

A real number like "*a*" exists so that _{} generating prime numbers.

After Mills this theorem extended by Kuipers in below form.

For every integer number_{} a
real number like "*a*" exists so that _{}generating
prime numbers, later the obligation of integrity for "*c*",
became removed.

If _{} be a real number, then a
real number like "*a*" exists that _{}generating prime numbers . At last Niven proved
below theorem:

For every real number _{} a real
number like "*a*" exists so that _{}generate
prime numbers.

Note that real number "*a*" in above theorems
isn’t unique.

Till now, we mentioned some attempts for finding a formula
to define _{}and also finding functions that
their values exclusively be prime numbers for natural numbers. In this subject,
we express some of results, obtained recently. As it clears soon, obtained
results although they are charming and pretty, but couldn’t solve the problem.
Origin of them is pretty Mills’s theorem (1947). But for training reasons, at
first, we express some of simple results that for proving them, it isn’t
necessary to be acquainting with primary properties of sequence and real
numbers set. Some Primary Results:

If:

_{} (1)

Then:

_{}
(2)

**Proof.** We know that_{}. So
series in formula (1) is concurrent:

_{}

But:

_{}

_{}

So:

_{}

And it is clear that

_{}

Therefore:

_{}.

Formula (2) of above theorem hasn’t useful advantage.

Because, for calculating "_{}"
by this formula, it must calculate value of "_{}"to
_{} digits of decimal and this
need to know the values of_{}.

Another formula also exists that
has this defect. For example, another
interesting formula that was found for finding _{}prime
number by using the prime numbers less than it was propounded by Gandhi in
Moscow Mathematicians congress in 1966.

If "_{}" is considered as n^{th}
prime number and (_{}) as obvious function and _{} then _{} is
calculated from the below inequality:

_{}

For every real number
"*a*", maximum one integer number "*k"* can be
found so that:

_{}

**Proof.** For proving this theorem, we put:

_{}

So:

_{}

That "_{}", but for every "_{}", the term _{}appears in above sum when "*d*"
is a common divisor of "*Q*" and "*t*". So,
coefficient of "_{}" in this sum is:

_{}

But we know:

_{} So _{} (according
to _{})

And now:

_{}

According to_{}, for every integer number "*m*"
that_{}, a prime number smaller than _{ }aliquots (_{}). So, the greatest "*t*"
which appears in _{}is (_{}). On
other side:

_{}

Therefore:

_{}

And with multiply this
relation in _{}

_{}

According to values of
"*P*" and "*S*", it is obvious that this
inequality is favorable inequality.

Mills’s theorem is based on below theorem:

Constant number like
"*A*" exists, so that for every natural number "*n*":

Proving Ingam’s theorem
by properties of Riemann zeta function (_{}) is more than
frame of this book. For proving next assertion, we accept it. In below, "*A*"
means Ingam's constant.

For every natural number
"*N*" that is greater than _{"}",
a prime number exists between _{}and_{}.

**Proof.** We suppose that _{}and
"_{}" is the greatest prime
number which is smaller than "_{}". So, from
theorem (6.5.5):

_{}

A real number
which we call it _{"" }exists so that _{ }is prime number for all
natural values of "*n*".

**Proof.** We define "_{}"
by a sequence of prime numbers. We consider that "_{}"
be a prime number greater than "*A*". According to (6.5.6), a
prime number exists between "_{}" and
"_{}". We choose one of them and
named it "_{}". Generally, if prime number
"_{}" is defined, we consider
that _{} is one of prime numbers
between "_{}" and "_{}" and _{}.

Now, we define _{}and _{} sequences
with below equalities:

_{}

_{} Sequence is instinctually ascending and _{} sequence is instinctually
descending. Because:

_{
}, _{}.

Always_{ }. It is clear that two sequences
are convergent and If_{}, then always _{ }so
_{}and according to (6.5.6):

_{}

Therefore for every
natural "*n"*:

_{}

Although proof of Mills’s pretty theorem indicates a method to define
"_{}" for making _{ }sequence that "_{}" is defined by it, we must
obtain prime numbers which are great at pleasure and this needs to have a kind
of formula for finding prime numbers. Mills’s theorem is developable. First extension of it was propounded by Kuipers
who in 1950 proved that "3" hasn't fundamental role in Mills’s theorem.

If "*c*"
be an arbitrary integer number greater than "2"_{}then
a real number like "_{}" exists so that _{} is prime for every natural
number "*n*".

**Proof.** Proving the theorem is the same as prove of Mills’s theorem with a little change. If we suppose
that _{} and_{},
then _{}So according to Ingam's theorem, a
constant number like "*B*" exists so that for every natural
number "*n*": _{}. Now, we
consider that "*N*" be a natural number and greater than "*B*"
and "_{}" be the greatest prime
number smaller than_{}. According to _{},
_{}. We will have:

_{}.

Now, we can define the
sequence of prime numbers _{}like proof of
Mills’s theorem by below relation:

And finish the proof in the same method.

It is proved that
for every_{}:_{ }

_{}

If "_{}" be r-th prime number, it is
proved that if _{} then, a prime number like
"*q*" exists so that:

Is there any polynomial so that answer the previous problem? Before expressing final result, we explain a little in this section.

**I.** If "*p*" be a prime number, value
of_{}, constant polynomial, is prime
for all of values of "*x*", we delete this trivial case form
this subject suppose that

_{}

Is a polynomial of first degree? If value of this polynomial be prime

number "*p*".
For_{ } we suppose that _{}then:

_{}

Then for every value of
"*k*" so that _{}is a composite
number, therefore it is impossible that the value of polynomial with integer
coefficients from first degree be a prime number for all of integer values or
positive and integer values of variable. Moreover, in this case, searching
about terms value of _{} for integer values of "*x*"
refers to arithmetic progression from integer numbers.

**II.** Some of second degree polynomials give long
sequence of prime numbers. For example below three polynomials (Euler, 1772)
that values of every one, are prime for integer values of "*x*"
that is determined:

_{}

Values of _{}polynomial are prime number for_{}.

If we suppose that _{} it is clear simply:

_{}

So, _{}is
prime for _{}and therefore _{}is
prime for _{}and finally the values of below
polynomial:

is prime for _{} namely _{},
but it is not necessary to be distinct. Because, for every value of "*x*":

Some of mathematicians
named "*m*" natural numbers as fortunate, when values of
polynomial _{ }are prime number for _{}values of "*x*".
From what is said above, it is clear that "41" is fortunate.
Moreover, simply we can search that 2, 3,5,11 and 17 also are fortunate. In
1934, Hailberon and Linfot proved that just one of other fortunate number
exists. And with calculation, it cleared that if such number exists, it will be
very great. At last, in 1967 Setark proved that fortunate numbers are just such
mentioned numbers.

It is clear that every non-constant polynomial with integer coefficients, assumes non- prime values. Proving below exact theorem is easy.

If _{} be
a non-constant polynomial with integer coefficients, set of integer numbers
like "*x*" that for them, _{} is
composite, is infinite.

**Proof.** We consider below polynomial has integer
coefficients:

_{}
(1)

And for every integer number
like "_{}", _{}be
prime. So, infinite integer number like "_{}"
exist that _{}is a composite number.

And also:

_{}

That _{}is
an integer coefficients polynomial with respect to "*y*".
Specially leading term _{}is_{}. So
according to (1):

_{}

By interpolation the formula of LaGrange, always we can make a polynomial that for every number of determined arbitrary integer values of variable, its values be difference prime numbers. For example value of below polynomial:

_{} for _{} values of
"*x*" respectively are equal to 3, 5, 7, 11, 13 and 17. But we
don't know a polynomial of second degree or more than it that we can prove that
its values are prime number for infinite numbers of "*x*"
values. Specially yet we don’t know that _{}polynomial has
this properties or not. In this section there are some simple necessary
conditions that we explain them below.

In order that values of
non-constant polynomial with integer coefficients _{} be
prime for infinite integer values of "*x*", necessary condition
is that _{} be irreducible. It means
that it isn’t decomposable to multiplication of two non-constant polynomials
with integer coefficients.

Polynomial with respect
to _{} variable doesn't exist that
its values be prime number for all of integer values of variables. In this field,
Yuri Matijasevich, Russian famous mathematician, in 1970, obtained a wonderful
result that polynomial with respect to some variable exists so that all of its
positive values are prime and in 1971, by using of Fibonacci's numbers designed
for making a polynomial with respect to 24 variable and form 37 degree with
mentioned properties and in completing his article, increased variables to 27
variables. But decrease degree to 31. We must name some of other investigator
mathematicians that have interesting work in this field, like Martin Davis,
Julia Robinson and Hilary Putnam. In 1976, James J. Jones (Canada), Daihachiro
Sato (Canada), Hideo Wada (Japan) and Douglas wines (Canada) in an assay which
printed in **"American** **Mathematical Monthly** (Vol. 83, number 6)",
proved that set of prime numbers is adapted on set of polynomial's positive
values with 25-th degree polynomial with respect to 26 variable *a*, *b*,
*c*, ... *z* for all of non-negative integer values of variables.

This polynomial also takes negative values like (–76) (Quoted from mentioned assay).

We suppose:

_{}

_{} (1)

So for every two natural
numbers, "*x*" and "*y*", _{} is
prime and moreover, when "*x*" and "*y*" run set
of natural number, _{} gives every prime number and
gives every odd prime number just one time.

**Proof.** We observe that values of _{} are
just 2 and_{}, because _{}if
_{}, then _{}.
According to definition of "_{}":

(2)
_{} ,
(3) _{}.

In first case _{} is
a prime number. In second case according to definition of "*B*",_{}then_{}. So
according to converse of Wilson's theorem, _{} is
a prime number. So, it is clear that for every two natural number "*x*"
and "*y*", value of _{} is a prime
number. Conversely, it clears that

f (1, 1) =2. If "*p*"
be an odd prime numbers, with definition of_{}:

_{}

So, _{} gives
all of prime numbers. At last, for proving this assertion "Just one
times" about odd prime number, It is enough to observe that according to
what we said, if odd prime number "*p*", from _{}, be obtainable, it must: _{} and therefore _{}and so:

_{}

then _{} take
value of "*p*" Just for value of "*x*" and _{} from "*y*".

At last we have to say
that it is wonderful that a mathematician like Hardy[2]
couldn't calculate such formulas that even he thought that such formulas don't
exist. Because in a speech in 1928 in America, he said that for example
"If some body wants me to write a formula for n^{th} prime number
or calculate "_{}" with respect to "_{}", only I can say that he ask
an erroneous question and probably such formula doesn't exist". I wish he
content oneself with this sentence then he presented formulas and explanation
to show that such formulas must not exist. Of course this speech was so important
and later put it in collection of articles of MAA, that takes prize (The
Chauvenet Papers). But it isn't credible that a formula which its existence
needs just Wilson's theorem, be so far from mind of a mathematician like Hardy.
If Hardy was alive now, he couldn't believe that he said such things sometimes.

In searching a rule that
be commanding of prime numbers distribution, decisive stage traversed when
mathematicians gave up useless trying for finding a simple mathematics formula
that generating "all" of prime numbers and dispensed with definition
real number of prime numbers that exists firstly on unit between "*n*"
successive numbers and instead of them, attempts to obtain information about
"average rate" of prime numbers distribution among "all"
numbers.