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 nth 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 nth 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 (Mp=2p-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 nth 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 nth 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.