Init jeu. dec. 30 11:20:36 CET 2010 ver. sam. jan. 1 12:34:58 CET 2011 ver. dim. jan. 2 17:56:55 CET 2011 ver. mar. jan. 4 11:03:45 CET 2011 ver. mer. jan. 5 15:15:34 CET 2011 ver. dim. jul. 3 14:19:47 CEST 2011 ver. mer. mai 29 07:10:37 CEST 2013 ver. jeu. mai 30 06:10:00 CEST 2013 : added JS eval+popups ver. ven. mai 31 09:45:48 CEST 2013 : found a direct relationship between index=>gap ver. sam. juin 1 05:41:03 CEST 2013 common tools for TPC & Goldbach ? ver. dim. juin 2 06:16:57 CEST 2013 Square Rooooot !!! ver. lun. juin 3 04:07:37 CEST 2013 formule de la population des roues !!! ver. lun sept 23 06:18:19 CEST 2013 C'est reparti... ver. mar. nov. 26 00:47:32 CET 2013 Status : PRELIMINARY AND INCOMPLETE, a lot of illustrations are needed too !

Best viewed with JavaScript enabled.

Category : Algorithmic Number Theory, Computational Number Theory

We examine wheel sieve-like algorithms that generate the sequence of the prime numbers. Our wheels compute "gaps", the differences between consecutive prime numbers. We focus on algorithmic simplicity and not on computational efficiency, so we can examine meaningful properties and structures that help prove the de Polignac Conjecture and its sibling: the Twin Prime numbers Conjecture.

__This page is dynamic__: you can directly run the JavaScript
source code by clicking on the greyed code paragraphs. This ensures that

* there is no discrepancy between the text and the actual functioning algorithms,

* you can test the programs indepedently, copy-paste-modify them and play at will

* you can actually understand the programs because they are written in a subset of one of the most
deployed languages without having to install any additional software or to learn an obscure,
niche dialect.

The de Polignac Conjecture
(dPC) states that there is an infinity of primes *p*
where the next prime *q* is equal to *p*+2*n* (with *n* integer >= 1).
The Twin Primes conjecture
(or TPC) is a special case (the most famous) of the de Polignac Conjecture where *n*=1.
The first twin prime pairs are the sequence A077800 in OEIS:

` (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ...`

These conjectures focus on the properties of the differences between consecutive primes ("prime gaps" or simply "gaps"). This study furthers an algorithmic approach (introduced in GLMF#121 in 2009) based on the construction and analysis of gap-generating algorithms. If the dPC is true, it follows that these algorithms generate an infinity of any gap. We try to build them in ways that make this property obvious and exploit it.

The gap 2 is often used as an example because the TPC is considered "difficult". As of 2013-06, the smallest infinitely repeating gap was demonstrated to be at most "70 millions" by Zhang Yitang. This was later reduced to about 600 by James Maynard but as of 2013-11, the gap is still not 2. The approach explained in this text is different and totally constrained in ℕ, the algorithms and their properties work without concern of the size of the numbers and no approximation could introduce uncertainty. Moreover, only basic operations are used (mostly additions of natural integers and some multiplies).

We will start with the study of certain "modified wheel sieves",
derived from previous publications by myself (GLMF#121 2009, see *Alg. 11*) then
Steve Maddox (2010, see *Alg. 12*).
These particular wheel sieves are ideal for the study of the dPC because they
differ from Paul Pritchard's and other's works in how informations are represented :
the "wheel" contains not the value of a prime candidate,
but the differences between prime candidates.

Another wheel sieve is also introduced, bringing even more insight and determinism, allowing us to extract and exploit more properties directly. The enhanced algorithm exploits and exposes the structure of the "interference patterns" of the wheel, which removes any concern about a "numbers conspiracy", the key to strengthen the proof of dPC and TPC.

And now, let's see how we can generate prime numbers.

Let us now define the basic tools that we use here.

• We will only use numbers that belong to ℕ (positive integer numbers from zero to infinity) with one practical exception (a negative number that helps simplify the algorithm at one point).

• All the algorithms described here must be able to take place in a hypothetical Universal Turing Machine ("UTM") capable of infinite storage of infinite integer numbers and infinite running time.

• This UTM must be able to perform at least the following operations on integer numbers :

- incrementation (add one to a number)
- addition
- multiplication
- comparison (is A less than, equal, greater than B ?)
- store to memory (to a calculated address)
- fetch from memory (from a calculated address)

• This UTM must support the following basic program flow control features :

- sequential execution (perform operation A then B then C...)
- if-then-else (conditional execution of a sequence)
- for-loop (iterative execution of a sequence)

In practice, such a UTM does not exist because our world is bounded in size, energy and time. However, at a small scale, it can be emulated by any programmable, general purpose computer, which can use any suitable programming language. In this demonstration, the algorithms will be represented in the JavaScript language because it is very widely supported. Readers can follow the examples and reproduce the data using their own web browser, thanks to embedded code that executes selected portions of this page. Clicking on an algorithm executes it and displays the result(s). Because the syntax and semantic are very close, translation to C and Java is straight-forward, and easy to Python, Perl, bash, Pascal, FORTRAN, PARI, Haskell, Mathematica or any other Turing-complete language.

Of course, JavaScript has some inherent limitations but they are carefully avoided by letting the code use only the features described above.

- Automatic memory allocation is avoided (the algorithms could be compiled)
- Numbers remain strictly integer by limiting the range from -2
^{31}to 2^{31}-1 (JavaScript uses IEEE754 64-bits floating point otherwise and this must be avoided). - Operations that might create non-integer numbers, such as division, are not allowed. This keeps any floating point number or character string from creeping in the computations. Boolean operations and shifts could be used however because they are bit-exact.
- By keeping the syntax and semantic as close to C as possible, no side effect is hidden from our view by syntactic sugar.
- No pointer, system call, library function or external help is used (except to display the results).

Here is a summary of the syntax used in this document :

This part is not meant to be a JavaScript tutorial but the above subset is enough to create prime numbers.

Using only this syntax, let's program the UTM to generate the whole set of ℕ^{0}=[0, 1, 2, 3, 4... ] in its memory.

A Turing Machine performs one operation at a time, its memory may not be completely initialised to a known state and it requires an iterative process that fills each memory slot one by one. The corresponding program may be expressed in this way :

var MAX = 200; // create the set ℕ^{0}var N = new Array(); // Note: when no size is specified, the array is unbounded // and extended when a write occurs beyond the current size. var a; // Loop: for (a=0; a < MAX; a++) { N[a] = a; } // displayN"N=["+N.join(", ")+" ...]";

Each iteration of this program computes the next integer number in `a` and writes
it to memory at the corresponding index. The result is a sorted, increasing list of numbers
in the array `N` where each number differs from the next one by 1.

This algorithm can be adapted to create the set of the even numbers. There are infinitely many algorithms that create the same output but here are three of the simplest versions that generate even numbers.

var MAX = 100; var b, c; // First version using absolute relationship // between the index and the value var E = new Array(); for (b=0; b < MAX; b++) { E[b] = 2*b; } // Second version using a relative relationship // (difference between consecutive values) var F = new Array(); c=0; for (b=0; b < MAX; b++) { F[b] = c; c = c+2; } // Third version where the loop counter generates // the value and an index must be computed var G = new Array(); c=0; for (b=0; b < MAX; b=b+2) { G[c++] = b; } // display E, F and G "E=["+E.join(", ")+" ...]\n\n"+ "F=["+F.join(", ")+" ...]\n\n"+ "G=["+G.join(", ")+" ...]";

One version of the algorithm may be chosen depending on convenience, clarity and other requirements, such as the range of indexes or the availability of one variable's value for other purposes.

These algorithms are combined to create the set of the prime numbers
**P** using Eratosthenes' method. It is simplified a bit because we
work with infinite sets, no need to stop the computation at the square root of the array's size.
The following simplified version is not computationally optimal when the set is finite (bounded by a real computer's memory)
but this is not a concern here, as long as the result is exact with any set size.

// Sieve of Eratosthenes in JavaScript var MAX = 1000; var N = new Array(), P = new Array(), prime, // the current prime index, // index in N pn=0; // number of primes found // Create the set ℕ^{0}for (index=0; index < MAX; index++) { N[index] = index; } // Select the first prime as 2 for (prime=2; prime < MAX; ) { // prime is updated at the end of the loop P[pn++] = prime; // Add the current prime toP// Mark all multiples of the prime as 0 for (index = prime*2; index < MAX; index = index + prime) { N[index] = 0; } // Advance to the next prime for (prime=prime+1 ; (prime < MAX) && (N[prime] == 0); prime++) { } } // displayPpn+" primes below "+MAX+": "+P.join(", ");

If you are bothered that an inner infinite loop might keep the outer infinite loop from
progressing, then imagine that our UTM is also a Rapidly Accelerating Computer (RAC) with
a clock working in Cantor time.
See an introduction in The Dynamics of Impossible Devices
by Ian Stewart, inventor of *infinormatics* in 1987.

Algorithm 3 has been adapted and optimised for specific computers, to create some of the fastest prime-generating programs.

However there are cases where one needs a list of consecutive numbers instead
of a sparse array of numbers that may or may not be prime.
There is also the situation where one wants to speed up the sieve by creating
not ℕ^{0} but a pre-sieved subset **S _{n}** where the

More fundamentally, the sieve of Eratosthenes tells us what a prime number is not (a prime is not a composite),
instead of what it is. Wheel sieves, on the contrary, generate primes instead of removing non-primes,
which brings more insight in the structure of **P**.

Let us just consider the case of pre-sieving ℕ. We can start by removing all the even numbers after 2, using code from Algorithm 2.

var MAX = 100; // All the odd integers > 2 var S2 = new Array(); var b, c=3; for (b=0; b < MAX; b++) { S2[b] = c; c = c+2; } // display pre-sieved S2 "S2=["+S2.join(", ")+" ...]";

The computational cost has been cut in half. It can get better if we pre-sieve if further with the value 3. However we have to take into account the even numbers that we have already sieved. We can't just keep every 3 number, because one half is even and must be skipped. The body of the loop becomes a bit more complex :

var MAX = 100; // Integers > 3 that are not multiple of 2 or 3 var S3 = new Array(); var b, c=5; for (b=0; b < MAX;) { S3[b++] = c; c = c+2; S3[b++] = c; c = c+4; } // display pre-sieved S3 "S3=["+S3.join(", ")+" ...]";

The set of sievable numbers is now 2/6 of the original set. Even more gain is possible by writing more complex code :

var MAX = 100; // Integers > 5 that are not multiple of 2, 3 or 5 var S5 = new Array(); var b, c=7; for (b=0; b < MAX;) { S5[b++] = c; c = c+4; S5[b++] = c; c = c+2; S5[b++] = c; c = c+4; S5[b++] = c; c = c+2; S5[b++] = c; c = c+4; S5[b++] = c; c = c+6; S5[b++] = c; c = c+2; S5[b++] = c; c = c+6; } // display pre-sieved S5 "S5=["+S5.join(", ")+" ...]";

As the program becomes more complex by integrating more constants, it must be reorganised by separating these constants into a specific structure. A new version, Algorithm 7 does just that.

We identify the constants with the *gaps* between consecutive prime
candidates. The cyclic table is the *wheel* that we want to study.
The loop continuously reads the wheel and adds each new number to
an accumulator, that contains consecutive numbers that have good
chances to be primes.

var MAX = 100; var S5 = new Array(); // create and initialise the array of gaps : var W5 = [ 4, 2, 4, 2, 4, 6, 2, 6 ]; var a=0, b, c=7; for (b=0; b < MAX;) { S5[b++] = c; c = c + W5[a++]; if (a >= W5.length) { // simulate circular addressing a = 0; } } "S5=["+S5.join(", ")+" ...]";

Algorithm 7 has moved some of the structure of
the prime numbers from code to constant data. It becomes more independent on
the actual level of pre-sieving and it can use any wheel.
We can convert Algorithm 4 into the wheel W_{2}=[2],
and Algorithm 5 into the wheel W_{3}=[2,4].
ℕ can even be created with W_{1}=[1].

To become totally independent of the pre-sieving level,
the initial value of the variable `c` must depend only on the wheel.
In Maddox's wheel algorithm, `c` can be set to **1** because the wheel is rotated
by one position (compared to Algorithm 7) so the last element becomes the first.
It appears that this last element, when incremented, becomes
the *next valid prime*. The code must also be modified to
account for the small rotation (accumulation occurs before
writing the result). These are little details that are not functionally
important but are critical for showing certain properties.

var MAX = 100; var S5 = new Array(); var W5 = [ 6, 4, 2, 4, 2, 4, 6, 2 ]; var a=0, b, c=1; for (b=0; b < MAX;) { c = c + W5[a++]; if (a >= W5.length) { a = 0; } S5[b++] = c; } "S5=["+S5.join(", ")+" ...]";

Algorithm 8 may be considered as a pseudoprimes generator
and its sieving efficiency depends only on the provided wheel. It is not really interesting by
itself because it provides no information about the structure of **P**.
It just "turns the wheel" to create pseudoprimes that must be further sieved.
All the structure is contained in the wheels, that we will now study.

One important property that we have just seen is that the next prime is obtained by incrementing the first element of the wheel.
This is a true for the other (adjusted) wheels, even W_{1}. One can even start from 0:

0+1 = 1 : W_{1}= [1]; 1+1 = 2 : W_{2}= [2]; 2+1 = 3 : W_{3}= [4, 2 ]; 4+1 = 5 : W_{5}= [6, 4, 2, 4, 2, 4, 6, 2 ]; OEIS A145011 "First differences of A007775." (repeated infinitely) 6+1 = 7 : W_{7}= [10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2 ]; A049296 "First differences of A008364. Also first differences of reduced residue system (RRS) for 4th primorial number, A002110(4)=210.

One wheel can yield the next prime number, and a whole family of algorithms can also yield the next wheel.
With these algorithms, it becomes possible to iterate the creation of wheels and build **P** in our hypothetical computer
(and a small, finite version in a desktop computer).

The description page of the sequence A049296
(concerning the wheel W_{7}) contains the following comments, which bring a lot of
interesting and useful informations :

"*First differences of reduced residue systems modulo primorial numbers are essentially palindromic + 1 separator term (2).
The palindromic part starts and ends with p_(n+1)-1 for the n-th primorial number.*"

→ This first comment says that our wheels have a *palindromic* structure: they are symmetrical
(which is also mentioned there).
They also *all* contain the number **2** as a *separator*, which is the second symmetry point. This particular value
is quite interesting since we are concerned with the TPC, but even more interesting is that
it is known that the first and last numbers are indeed p_(n+1)-1, or the next prime minus one
(no proof is needed here). The notion of "primorial" also appears (see below).

"*This sequence has period A005867(4)=A000010(A002110(4))=48. The 0th, first, 2nd and 3rd
similar difference sequences are as follows: {1},{2},{4,2},{6,4,2,4,2,4,6,2} obtained from
reduced residue systems of consecutive primorials.*"

→ In other words : W_{1}, W_{2}, W_{3}, W_{5} and others are well studied and
their primorial sizes are well defined (see below).

"*Difference sequence of the "4th diatomic sequence" - A. de Polignac (1849), J. Dechamps (1907).*"

→ People have been looking at it for ages, including the author of the conjecture that is the subject of this study.

There are two other important properties, suggested by the OEIS comments :

__Sum of the gaps:__

ƩThe sequence [ 1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, ... ] is OEIS A002110 "_{1}= 1 Ʃ_{2}= 2 Ʃ_{3}= 6 Ʃ_{5}= 30 Ʃ_{7}= 210 Ʃ_{11}= 2310 Ʃ_{13}= 30030 Ʃ_{17}= 510510 Ʃ_{19}= 9699690 Ʃ_{23}= 223092870

It is easy to understand : each wheel keeps numbers that are not multiple of all the smaller wheels. For example, W

__Number of gaps per wheel__

length(WThe sequence [ 1, 2, 8, 48, 480, 5760, 92160, 1658880, 36495360 ...] is OEIS A005867 "_{1}) = 1 length(W_{2}) = 1 length(W_{3}) = 2 length(W_{5}) = 8 length(W_{7}) = 48 length(W_{11}) = 480 length(W_{13}) = 5760 length(W_{17}) = 92160 length(W_{19}) = 1658880 length(W_{23}) = 36495360

For example :

These properties let us see that the wheels are well structured (at least externally),
so an algorithm may be written to generate a new working wheel from any given working wheel.
Of course, a bad wheel will generate another bad wheel but this is easily detected because
the generated numbers are not primes, or the wheel doesn't satisfy the above properties
(broken symmetry, length≠phi or Ʃ_{n}≠n#).

A new wheel W' can be created from a given wheel W by a three steps algorithm : **generation**, **replication** and **merge**.

**generation**generates the next new prime*p'*. Take the first element of the wheel W (W[0]) and add**1**.*p'*= W[0] + 1

This is already done by the first iteration of Algorithm 8.**replication**creates the new wheel W' by concatenating the precedent wheel*p'*times.

For example, W_{3}=*p'*× W_{2}= 5 × [ 4, 2 ] = [ 4, 2, 4, 2, 4, 2, 4, 2, 4, 2 ]**merge**adds and merges pairs of numbers that would create multiples of*p'*. This shrinks W' by removing length(W) gaps. It is the most subtle part that also brings the most insight in the primes' recursive structure.

Let's now write code that translates these ideas into operations :

W = // Select one starting wheel : // [ 1 ]; // [ 2 ]; // [ 4, 2 ]; [ 6, 4, 2, 4, 2, 4, 6, 2 ]; // [ 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2 ]; var L = W.length; var L2; // Step 1: generate var p = W[0] + 1; // Step 2: replicate var L2 = p * L; var W2 = new Array(L2); var i, j=0; // iterate over the whole new wheel for (i=0; i<L2; i++) { // copy from W to W2 W2[i] = W[j++]; // circular addressing (loop inside W) if (j >= L) { j=0; } } // Step 3: merge var W3 = new Array(); var acc = -W2[0]; // accumulator for the congruence // Note that it is a negative value // to force merge at the 2nd iteration // iterate again j=0; for (i=0; i<L2;) { if (acc == 0) { // merge with the precedent gap W3[j-1] = W3[j-1] + W2[i]; // Don't update j here } else { // just copy and advance j W3[j++] = W2[i]; } acc = acc + W2[i++]; // compute modulo manually for ( ; acc >= p; ){ acc = acc - p; } } "New prime: "+p+"\nNew size: "+j+"\nNew wheel: ["+W3.join(", ")+"]";

The most delicate part is the step 3, which scans through all the unmerged gaps and accumulates them. The accumulator is constantly kept below the current prime number with successive subtractions to emulate a modulo operation. When the accumulator is equal to zero, it means that the accumulated gaps reaches a multiple of the current prime, so the current gap must be merged with the precedent gap.

The accumulator is initialised with the negative of the first gap, so the merge occurs when encountering the second gap. This is the only place where a negative number is needed. A positive-only version would be more cumbersome and require more code, making analysis uselessly more complex.

Note that the expression W3[j-1] can not access the array outside of its range because the accumulator is initialised with a negative value. This prevents the merge from happening during the first iteration where a negative index would result in an error.

The code size can be reduced by merging the step 2 and step 3. This results in a single loop where the merge can occur while replicating the original wheel. Some variables' names have changed, the loop counter is different, but the result remains identical.

W = // Select one starting wheel : // [ 1 ]; // [ 2 ]; [ 4, 2 ]; // [ 6, 4, 2, 4, 2, 4, 6, 2 ]; // [ 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2 ]; var L = W.length; // Step 1: generate var p = W[0] + 1; // Step 2 and 3: replicate and merge in a single loop var L2 = W[0] * L; var W2 = new Array(L2); var i=0, j=0, k; var acc = -W[0]; // accumulator for the congruence // Note that it is a negative value // to force merge at the 2nd iteration var L3 = p * L; // This is necessary so it works with W=[1] for (k=0; k<L3; k++) { if (acc == 0) { // merge with the precedent gap W2[j-1] = W2[j-1] + W[i]; // Don't update j here } else { // just copy and advance j W2[j++] = W[i]; } acc = acc + W[i++]; // compute modulo manually for ( ; acc >= p; ){ acc = acc - p; } // circular addressing (loop inside W) if (i >= L) { i=0; } } "New prime: "+p+"\nNew size: "+j+"\nNew wheel: ["+W2.join(", ")+"]";

Now that we can transform a wheel into another, we can repeat the code inside a loop and generate consecutive wheels.

W = [ 1 ]; // Start as simply as possible var L = 1; // Length of the original wheel var p = 1; // Prime number whose wheel is being built var W2; // The new wheel var L2; // Length of the new wheel var i, j, k;// indexes, counters var acc ; // accumulator for the congruence var L3; // Loop var m=""; // Store messages (displayed in the end) var MAX = 11; // generates primes up to 11 for ( ; p < MAX ; ) { p = W[0] + 1; // generate L2 = W[0] * L; W2 = new Array(L2); i=0; j=0; acc = -W[0]; // accumulator for the congruence L3 = p * L; for (k=0; k<L3; k++) { if (acc == 0) { W2[j-1] = W2[j-1] + W[i]; // merge with the precedent gap } else { W2[j++] = W[i]; // just copy and advance j } acc = acc + W[i++]; for ( ; acc >= p; ){ acc = acc - p; // manual modulo } // circular addressing (loop inside W) if (i >= L) { i=0; } } L = L2; W = W2; // copy the new array into the first // one so it can be reused during the next iteration // log the current computation results for later m+="New prime: "+p+"\nNew size: "+L+"\nNew wheel: ["+W.join(", ")+"]\n\n"; } m;

MAX is kept low because the chosen JavaScript display system is saturated very fast.
The practical wheel size limit for today's desktop browsers is *p*=23, which would occupy 400MB.
The next prime number 27 would require about 11GB of RAM because our integer numbers are represented
as (denormalized) 64-bits IEEE754 numbers, plus all the internal hashtable bookkeeping. Programming in C would give a better density.
In the infinite UTM, however, this program will generate the whole set of **P**,
regardless of the size of the wheels.

Yet *Alg. 11* still contains the same deficiency
as *Alg. 3*: the code's execution path is
"data driven". This is due to the merge step that scans through the wheel
in search of congruent gaps, without showing any explicit structure,
just like the sieve of Eratosthenes. Merges should happen "there" because
the places are congruent but we don't know why there and not here.
Is there a formula to predict where a merge will occur ? Not exactly
but we'll see that it's not as complex as it seems.

Observations (from Maddox's post in 2010 but probably discovered before in other ways)
reveal that the gap pairs are merged using informations from the original and symmetrical
wheel W, using simple calculations.
For example, transforming W_{5} into W_{7} creates the temporary W':

W' = (W_{5}[0]+1) × W_{5}= 7 × [ 6, 4, 2, 4, 2, 4, 6, 2 ] = [ 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2 ]

The differences with W_{7} appear there :

W' = [ 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2 ]

There are 8 merges, which is the length of W_{5} and matches Euler's phi formula.

Now let's accumulate the gaps between two merged pairs, starting from the second number of each pair.

6=> moved to the last line4 + 2 + 4 + 2 + 4 + 6 + 2 + 6 + 4 + 2 + 4 + 2 = 42 4 + 6 + 2 + 6 + 4 + 2 + 4 = 28 2 + 4 + 6 + 2 = 14 6 + 4 + 2 + 4 + 2 + 4 + 6 = 28 2 + 6 + 4 + 2 = 14 4 + 2 + 4 + 6 + 2 + 6 + 4 = 28 2 + 4 + 2 + 4 + 6 + 2 + 6 + 4 + 2 + 4 + 2 + 4 = 42 6 + 2 + (6) = 14

The symmetry is striking and a new order appears.
Why are there an equal number of merges on both halves of the wheel?
It is obviously due to another level of symmetry. The accumulated gaps between merged gaps (gap gap?)
gives the following sequence :`
[ 42, 28, 14, 28, 14, 28, 42, 14 ]
`

When each of these gaps is divided by the current prime *p*, we obtain the original wheel W :

[ 42, 28, 14, 28, 14, 28, 42, 14 ] / 7 = [ 6, 4, 2, 4, 2, 4, 6, 2 ]

This simple relationship also appears with all the other studied wheels. It also explains the value of the first gap gap:
when added to *p*, it gives *p*^{2} which is the first composite (mod *p*), since
all the precedent gaps (from smaller primes) are already sieved out.

So the merges occur at very specific and deterministic locations. Let's use this information
to modify *Alg. 11*: the merge decisions are now taken with the help
of W, instead of a congruent accumulation.

W = [ 1 ]; // Start as simply as possible var L = 1; // Length of the original wheel var p = 1; // Prime number whose wheel is being built var W2; // The new wheel var L2; // Length of the new wheel var i, j, k;// indexes, counters var acc ; // accumulator for the congruence var L3; // Loop var r; // index inside W for the merges var m=""; // Store messages (displayed in the end) var MAX = 11; // generates primes up to 11 for ( ; p < MAX ; ) { p = W[0] + 1; // generate L2 = W[0] * L; L3 = p * L; W2 = new Array(L2); i=0; j=0; r=0; acc = W[0]; // don't merge right away for (k=0; k<L3; k++) { if (acc == 0) { W2[j-1] = W2[j-1] + W[i]; // merge with the precedent gap acc = p * W[r++]; // calculate the gap until the next merge : } else { W2[j++] = W[i]; // just copy and advance j } acc = acc - W[i++]; // it's a subtraction now // circular addressing (loop inside W) if (i >= L) { i=0; } } L = L2; W = W2; // copy the new array into the first // one so it can be reused during the next iteration // log the current computation results for later m+="New prime: "+p+"\nNew size: "+L+"\nNew wheel: ["+W.join(", ")+"]\n\n"; } m;

This algorithm is better than *Alg. 11* (published in 2009)
because it shows more explicitly that the wheel is a self-replicating structure.
Classic congruence has been replaced by a more precise and direct relationship between
the old and the new wheel.

This algorithm has been modified a bit in other places: the accumulator decreases instead of increasing, which simplifies a bit the code and we can start with a positive accumulator. When a merge occurs, the new accumulator value is calculated with the previously found relationship.

We have already seen that starting with W_{2}, the last number of a wheel is
always 2. It was called the "separator" and it is one point of symmetry of this circular structure.
But what are the properties of the other point of symmetry ?

This other point is at the middle of the original wheel W.
In our 0-based arrays (the first element is at index 0),
the middle is at index m=floor((length-1)/2). You can also
shift the binary integer right by one position to get this value.
The unmerged wheel Wu contains an odd number of copies W (for *p*>2),
so the middle of Wu *is* the middle of W.

*Proof : All primes p>2 are odd. So let's concatenate floor(p/2) times W before
and after a central W: each copy in a pair cancels each other, the symmetry is preserved and 4 remains in the middle.*

For example,

W_{u3} = *p'* × W_{2} = 5 × [ 4, 2 ]

= [ ~~4, 2~~, ~~4, 2~~, 4, 2, ~~4, 2~~, ~~4, 2~~ ]

After the merge, what is the value of the middle ? *Alg. 12* has been modified a
tiny bit to extract those values :

W = [ 1 ]; // Start as simply as possible var L = 1; // Length of the original wheel var p = 1; // Prime number whose wheel is being built var W2; // The new wheel var L2; // Length of the new wheel var i, j, k;// indexes, counters var acc ; // accumulator for the congruence var L3; // Loop var r; // index inside W for the merges var m=""; // Store messages (displayed in the end) var MAX = 17; // generates primes up to 17 for ( ; p < MAX ; ) { p = W[0] + 1; // generate L2 = W[0] * L; L3 = p * L; W2 = new Array(L2); i=0; j=0; r=0; acc = W[0]; // don't merge right away for (k=0; k<L3; k++) { if (acc == 0) { W2[j-1] = W2[j-1] + W[i]; // merge with the precedent gap acc = p * W[r++]; // calculate the gap until the next merge : } else { W2[j++] = W[i]; // just copy and advance j } acc = acc - W[i++]; // it's a subtraction now // circular addressing (loop inside W) if (i >= L) { i=0; } } L = L2; W = W2; // copy the new array into the first // one so it can be reused during the next iteration // log the current computation results for later m+="New prime: "+p+"\nNew size: "+L+"\nMiddle="+ W[(L-1)>>1]+"\n\n"; } m;

New prime: 2 New size: 1 Middle=2 New prime: 3 New size: 2 Middle=4 New prime: 5 New size: 8 Middle=4 New prime: 7 New size: 48 Middle=4 New prime: 11 New size: 480 Middle=4 New prime: 13 New size: 5760 Middle=4 New prime: 17 New size: 92160 Middle=4 New prime: 19 New size: 1658880 Middle=4 New prime: 23 New size: 36495360 Middle=4

Starting with W_{3}, the "middle" is always 4 and the previous proof
explains in part why there is no change to expect.
Since the merges are determined by the previous W which is symmetrical
(OEIS says it's palindromic) and W has an even size,
there are as many merges on both sides of the middle point
(so the middle is preserved).

If the size is odd (which happens only at the beginning) then the middle element gets merged.
This explains why the initial 1 of W_{1} disappears but all other elements get preserved
in all the following wheels.
*If 1 is the only element that is ever removed from the wheels, then this counts
as one interesting argument in favor of the de Polignac Conjecture.*

Work in progress. Stay tuned...

Paul Pritchard (Cornell University) has worked on wheel sieves since the 70s.

Improved Incremental Prime Number Sieves (1994)

`Abstract`

An algorithm due to Bengalloun that continuously enumerates the primes is adapted to give the first prime number sieve that is simultaneously sublinear, additive, and smoothly incremental:

-- it employs only \Theta(n= log log n) additions of numbers of size O(n) to enumerate the primes up to n, equalling the performance of the fastest known algorithms for fixed n;

-- the transition from n to n + 1 takes only O(1) additions of numbers of size O(n). (On average, of course, O(1) such additions increase the limit up to which all primes are known from n to n + \Theta(log log n)).

An algorithm due to Bengalloun that continuously enumerates the primes is adapted to give the first prime number sieve that is simultaneously sublinear, additive, and smoothly incremental:

-- it employs only \Theta(n= log log n) additions of numbers of size O(n) to enumerate the primes up to n, equalling the performance of the fastest known algorithms for fixed n;

-- the transition from n to n + 1 takes only O(1) additions of numbers of size O(n). (On average, of course, O(1) such additions increase the limit up to which all primes are known from n to n + \Theta(log log n)).

Many of the ideas of this text have been already explained (in french) in this article :

Un algorithme additif et itératif pour construire les Nombres Premiers

(*An additive and iterative algorithm for the construction of prime numbers*)

Published in kiosks in France : GNU/Linux Magazine #121 (11/2009)

Published online : 23/07/2010

License : CC-BY-ND

(

Published in kiosks in France : GNU/Linux Magazine #121 (11/2009)

Published online : 23/07/2010

License : CC-BY-ND

On July 21th, 2010, Steve Maddox posted the outline of his algorithm on the primenumbers@yahoogroups.com mailing list.

http://tech.groups.yahoo.com/group/primenumbers/message/21637

"Re: Formula that couples each composite number to one prime only"

gives a link to https://sites.google.com/site/primepatterns/

His message is mirrored here

It is not perfectly well explained but please read it. It is not long but requires some paper&pen time.

"Re: Formula that couples each composite number to one prime only"

gives a link to https://sites.google.com/site/primepatterns/

His message is mirrored here

It is not perfectly well explained but please read it. It is not long but requires some paper&pen time.

Stephen Maddox for sharing his insights, allowing the present work to evolve from 2009's limbo.