Professeur de
mathématiques et Docteur ès lettres
-
e-mail
Traduction Clémence
Godefroy
Article
déposé le 19 avril 2010. Editeur : Eric Vandendriessche. Toute
reproduction
pour publication ou à des
fins commerciales, de la totalité ou d'une partie de
l'article, devra
impérativement faire l'objet d'un accord
préalable avec l'éditeur (ENS
Ulm). Toute reproduction à des fins privées, ou
strictement
pédagogiques dans le cadre limité d'une
formation, de la totalité ou
d'une partie de l'article, est autorisée sous
réserve de la mention
explicite des références éditoriales
de l'article.
Une
version française de cet article a été
publiée par la Revue Tangente (n°108
, 2006). CultureMATH
remercie la Revue Tangente d'avoir autorisé
la publication de cette
version anglaise
This
article features a new type of algorithm whose goal is not to find
prime numbers like the Sieve of Eratosthenes, but to give a better
understanding of how they form themselves. It is called the
Prime-Generating Algorithm or PGA.
The length of numbers
The series of integers is generated by the number
“1” in an additive manner. In this succession of
numbers,
prime numbers seemingly appear without following a clear pattern. The
definition of a prime number being relevant to multiplication, the main
idea here is no longer to consider prime numbers as being additively
generated by 1, but multiplicatively generated by prime numbers, and to
sort them according to the prime number that features in the
decomposition of an integer. First, the length of the integer must be
defined : it’s the number of prime numbers involved in the
decomposition of one integer n into products of prime numbers (prime
factorization). For example, 12 = 2×2×3 has length
3.
Likewise, the length of 5 is 1. According to this definition, prime
numbers are integers whose length is 1.
Furthermore, integers can be placed in intervals limited by consecutive
powers of 2. Hence, of the form Ir
= [2r ; 2r+1[.
Notice that 2 is the smallest prime number. Therefore 2r is the smallest
integer of length r.
Every integer in the interval Ir
is smaller than 2r+1,
which is the smallest integer of length r+1. From this it
can be deduced that in the intervals Ir,
integers have a maximum length of r.
For the time being, we will allow that the integers’ lengths
take every value from 1 to r.
This enables us to classify integers according to their lengths in each
interval.
The following remarks can be made : the intervals Ir are all separate
and form a partition of the set N of natural numbers. Furthermore, the
number of elements in Ir
doubles when going from r
to r+1.
Our algorithm consists in writing integers according to this division.
The train will whistle
p times
Consider the PGA chart (Table
below) and observe the interval I4
: each length of I4
is generate by particular integers - the length 4 by 2 and 3 ; the
length 5 by 2, 3, 5, 7; the length of 2 by 2, 3, 5, 7, 11, 13. The
colors show that more of the same can be observed for the lengths of 5,
4 and 3 of I5
and the lengths of 2 and 3 for I3.
The algorithm could be represented in the following way :
each interval Ir
is a train. The new prime numbers are the engine, the old ones
constitute the wagons. The last wagon I4 is constituted by the prime numbers of
the interval I1,
2 and 3. Also note that the last wagon will always contain two elements
regardless of the interval (in I1000, there
are two numbers whose length is 1000). The prime numbers of I1
and I2
constitute the first-to-last wagon of I4(the numbers with a length of 3). The number of integers
in this wagon
is five and it is stabilized, that is to say that the number of
integers of the first-to-last wagon (the integers with a length of 4)
of the next train I5
is also five, as we can observe on the chart. Thus it can be shown that
in I100
the last thirty-six wagons have a stabilized number of integers (see
the stabilization theorem below).
Table
: The Prime-Generating Algorithm (PGA)
Lengths of integers
Intervals Ir
1
2
3
4
5
...
Io
=[20 ;
21[
1
I1
= [21 ;
22 [
2
3
I2
= [ 22 ;
23 [
5
7
2×3
2×2
I3
= [ 23 ;
24 [
11
13
2×5
2×7
3×5
3×3
2×2×2
2×2×3
I4
= [ 24 ;
25 [
17
19
23
29
31
2×11
2×13
3×7
5×5
2×3×3
2×2×5
2×3×5
2×2×7
3×3×3
2×2×2×2
2×2×2×3
I5
= [ 25 ;
26 [
37
41
43
47
53
59
61
2×31
2×29
2×23
2×19
2×17
3×19
3×17
3×13
3×11
5×11
5×7
7×7
2×2×11
2×2×13
2×3×7
3×3×5
3×3×7
2×5×5
2×2×2×5
2×2×2×7
2×2×3×3
2×2×3×5
2×3×3×3
2×2×2×2×2
2×2×2×2×3
...
Generated
by
2 ; 3 ; 5 ; 7 ; 11 et 13
Stabilized
to 5 integers
Generated
by
2
; 3 ; 5 et 7
Stabilized
to 2 integers
Generated
by
2 et 3
Theorems originating
from the PGA
We will only state two
results here : a
preliminary theorem that we will prove and a central theorem in this
study, the theorem of stabilization, that will not be shown.
Consider the interval Ir
= [2r ; 2r+1 [. Lr,m
denotes the integers of length m belonging
to Ir.
The integer m
varies therefore from 1 to r
(a strictly positive integer). We denote by Pr
= Lr,1
the prime numbers of Ir.
Card (Lr,m)
designates the number of prime numbers in Lr,m.
Preliminary theorem
A) The prime numbers q
which are factors of some integer in Lr,m
are such that : q
<
2 r - m
+ 2.
B) If q
is a prime number such that q
<
2 r - m
+ 2, there exists at least one integer in Lr,m,
with 2 ≤ m
≤ r , that contains q as a factor.
Proof
A)
Indeed, if q ≥
2 r - m
+ 2, then 2m-1q ≥
2r+1
.
However 2m-1q is the smallest
integer of length m
that contains q.
Thus there is no integer in Lr,m
containing q,
and we necessarily get q
<
2 r - m
+ 2.
To prove B, we need the following lemma.
Lemma
For every real number x ≥
2, a prime number between x and 2x can always be
found.
Proof
Bertrand’s postulate states that for every integer n > 1, a
prime number between n
and 2n can
always be found.
Consider a real number x,
with x ≥
2 and let E(x) be the integer
part of x.
We have E(x) > 1 and
according to Bertrand, there exists a prime number p such
as E(x) < p < 2 E(x), which implies E(x) +
1 ≤
p < 2E(x).
From E(x) ≤
x < E(x) +1, we deduce
that x
< E(x) +
1 ≤ p
< 2 E(x) ≤
2x,
which proves our assertion.
Proof B)
Consider now q
< 2 r - m
+ 2.
If 2 r
- m
+ 1 ≤
q
< 2 r - m
+ 2, then 2 r ≤
2
m
- 1 q
< 2 r - 1 ,
and so, in the case of 2 ≤
m
≤ r, there indeed exists at least one
integer of Lr,m
that contains q
as a factor.
If q
< 2 r - m
+ 1, then 2 r
- m
+ 1 /
q > 1 and 2 r - m
+ 2 /q
> 2.
Thus there exists a prime number p
between 2 r
- m
+ 2 /q
and 2 r
- m
+ 3 /q.
From this we deduce, using the lemma above, that in the case
of
2 ≤ m
≤ r, 2 m - 2pq belongs to Ir and
this number is indeed a integer of length m that contains q as a factor.
In other words, integers of length 2 ≤ m
≤ r of an interval Ir are
the spawn of all the prime numbers less than or equal to those of
the interval Ir
- m +1.
(It can be said that prime numbers generate a collection H of integers if
all of these prime numbers are to be found in the decomposition of H’s
integers and if there are no other).
Stabilization theorem
For every r
and m ≥
(r+1)ln2 / ln3 we
have card( Lr,m)=
card( Lr + n, m
+ n) for any natural number n. ( Proof
in the french version)
We can thus observe that for r
> 4, for than a third of the length of an interval Ir
have a cardinal number that stabilizes itself and therefore is also
part of following intervals. To give an idea of this, in I100,
the last 36 lengths are stabilized. One can calculate stable lengths.
Thus, for example, for every r > 7, it can easily be found
that Lr,r = 2, Lr,r - 1
= 5, Lr,r - 2
= 8, etc.
Conclusion :
Order rather than chaos
The PGA reveals a structure. In this algorithm,
the intervals Ir
appear to be generating cells of a collection of prime numbers which do
not show in the decomposition of elements of Ir
or of any of the previous intervals. On the other hand, these prime
numbers will be used in the integers of the next intervals: the
integers of length 2 in Ir+1,
the integers of length 3 in Ir+2
and so on until some length n is reached whose cardinal stabilizes. The
interval Ir
also appears to be related with the history of those prime
numbers
which have been constructed before. This clockwork looks closer to
order than to chaos. This new order appears to be ruled by rigorously
precise laws. Instead of focusing on a single prime number, one
considers instead the collection of all such primes which belong to a
given interval Ir.
Therefore we promote the idea of studying prime numbers through the
sieve provided by our intervals Ir.
Our algorithm therefore connects to enumeration problems and thus to
the paramount problem of estimating more precisely the density of prime
numbers. Understanding the integers of length 2, as depicted in our
PGA, is also relevant to cryptography problems. This glance towards the
future is a proper way to conclude this article.
References
Jacques Bienvenu, "L'algorithme de génération des
premiers (AGP)", Revue
Tangente, n°108, 2006