Professeur de
mathématiques et Docteur ès lettres

email
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
PrimeGenerating 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 I_{r}
= [2^{r} ; 2^{r+1}[.
Notice that 2 is the smallest prime number. Therefore 2^{r} is the smallest
integer of length r.
Every integer in the interval I_{r}
is smaller than 2^{r+1},
which is the smallest integer of length r+1. From this it
can be deduced that in the intervals I_{r},
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 I_{r}
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 I_{4}
: each length of I_{4}
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 I_{5}
and the lengths of 2 and 3 for I_{3}.
The algorithm could be represented in the following way :
each interval I_{r}
is a train. The new prime numbers are the engine, the old ones
constitute the wagons. The last wagon I_{4} is constituted by the prime numbers of
the interval I_{1},
2 and 3. Also note that the last wagon will always contain two elements
regardless of the interval (in I_{1000}, there
are two numbers whose length is 1000). The prime numbers of I_{1}
and I_{2}
constitute the firsttolast wagon of I_{4}(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 firsttolast wagon (the integers with a length of 4)
of the next train I_{5}
is also five, as we can observe on the chart. Thus it can be shown that
in I_{100}
the last thirtysix wagons have a stabilized number of integers (see
the stabilization theorem below).
Table
: The PrimeGenerating Algorithm (PGA)
Lengths of integers
Intervals I_{r}
1
2
3
4
5
...
I_{o}
=[2^{0 };
2^{1}[
1
I_{1}
= [2^{1} ;
2^{2} [
2
3
I_{2}
= [ 2^{2} ;
2^{3} [
5
7
2×3
2×2
I_{3}
= [ 2^{3} ;
2^{4} [
11
13
2×5
2×7
3×5
3×3
2×2×2
2×2×3
I_{4}
= [ 2^{4} ;
2^{5} [
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
I_{5}
= [ 2^{5} ;
2^{6} [
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 I_{r}
= [2^{r} ; 2^{r+1} [. L_{r,m}
denotes the integers of length m belonging
to I_{r}.
The integer m
varies therefore from 1 to r
(a strictly positive integer). We denote by P_{r}
= L_{r,}_{1}
the prime numbers of I_{r}.
Card (L_{r,m})
designates the number of prime numbers in L_{r,m}.
Preliminary theorem
A) The prime numbers q
which are factors of some integer in L_{r,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 L_{r,m},
with 2 ≤ m
≤ r , that contains q as a factor.
Proof
A)
Indeed, if q ≥
2 ^{r  m
+ 2}, then 2^{m1}q ≥
2^{r+1}
.
However 2^{m1}q is the smallest
integer of length m
that contains q.
Thus there is no integer in L_{r,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 L_{r,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  2}pq belongs to I_{r} 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 I_{r} are
the spawn of all the prime numbers less than or equal to those of
the interval I_{r}_{
 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( L_{r,m})=
card( L_{r + 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 I_{r}
have a cardinal number that stabilizes itself and therefore is also
part of following intervals. To give an idea of this, in I_{100},
the last 36 lengths are stabilized. One can calculate stable lengths.
Thus, for example, for every r > 7, it can easily be found
that L_{r,r} = 2, L_{r,r }_{ 1}
= 5, L_{r,r }_{ 2}
= 8, etc.
Conclusion :
Order rather than chaos
The PGA reveals a structure. In this algorithm,
the intervals I_{r}
appear to be generating cells of a collection of prime numbers which do
not show in the decomposition of elements of I_{r}
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 I_{r+}_{1},
the integers of length 3 in I_{r+2}
and so on until some length n is reached whose cardinal stabilizes. The
interval I_{r}
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 I_{r}.
Therefore we promote the idea of studying prime numbers through the
sieve provided by our intervals I_{r}.
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