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.