Traduction
Version [pdf] (1.06 Mo)
2. The train will whistle p times
3. Theorems originating from the PGA
Conclusion : Order rather than chaos
Table : The Prime-Generating Algorithm
| Lengths of integers | ||||||
|
|
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 |
|
|||
| I4 = [ 24 ; 25 [ |
19
23
29 |
2×13
3×7 |
2×2×5
2×3×5
2×2×7 |
|
||
| I5 = [ 25 ; 26 [ |
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×13
2×3×7
3×3×5
3×3×7 |
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
|
Stabilized
Generated |
Stabilized to 2 integers
Generated 2 et 3 |
|||
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 - 2 pq 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 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( 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.
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.