(C) Yann Guidon 2010-2013 / Only reproductions of exact copies are allowed for private, non commercial use (CC-BY-ND).
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 !


Wheel algorithms bring insight into the structure of the prime numbers

Yann Guidon (yg at ygdes dot com)

Best viewed with JavaScript enabled.

Category : Algorithmic Number Theory, Computational Number Theory

Summary

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.

 

 

Introduction

The de Polignac Conjecture (dPC) states that there is an infinity of primes p where the next prime q is equal to p+2n (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.

Algorithmic tools

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 :

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

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.

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

  • // Here is a one-line comment
  • /* Here is a multi-line comment */
  • // Declare 4 variables named a, b, c and d var a, b, c, d; // Their initial value is "undefined" // and they must be initialised before use.
  • // Simple assignations a = 2; b = 3;
  • // Post-incrementation b++; // The updated value is available at the next line.
  • // addition c = a + b;
  • // subtraction c = a - b;
  • // multiplication d = c * b;
  • // Note about using a number before assignation: var x; x = x+1; // this will return "NaN" (Not a Number) // which helps to spot certain bugs.
  • /* Create an array, or vector, or list, of 42 numbers (uninitialised), allocate memory from index 0 to index 41. */ var t = new Array(42);
  • // memory access t[5] = 425; // Store the value 425 at index 5 of array t var u = t[5]; // create the variable u // and initialise it by fetching the value at index 5 of array t
  • // Conditional execution : if (a < b) { // sequence of operations executed if a < b } else { // sequence of operations executed if a >= b }
  • // Iteration : for (a = 0; a < b; a++) { /* sequence of operations executed b times a is the loop counter that takes all the consecutive values between 0 and b (non inclusive) */ }
  • // JavaScript can represent the value "Infinity" ∞ : var MAX = Number.POSITIVE_INFINITY; // MAX will be the maximum // iteration count in the following code, so it can be changed // to a computer-friendly value in the interactive examples.
  • // The last line builds a character string that is displayed // when the user clicks on the algorithm. It is not considered // as a part of the UTM and is provided for convenience. "result = "+a;
  • This part is not meant to be a JavaScript tutorial but the above subset is enough to create prime numbers.

    Basic number generation algorithms

    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 :

    Alg. 1 : OEIS A001477 "The nonnegative integers."
    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;
    }
    
    // display N
    "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.

    Alg. 2 : OEIS A005843 "The even numbers: a(n) = 2n."
    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.

    Alg. 3 : OEIS A000040 "The prime numbers."
    // 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 to P
    
      // 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++) {
      }
    }
    
    // display P
    pn+" 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.

    From the sieve of Eratosthenes to wheel sieves

    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 Sn where the n smallest factors (that consume most of the computation cycles) are already removed.

    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.

    Alg. 4 : OEIS A005408 "The odd numbers: a(n) = 2n+1." (in fact 2n+3)
    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 :

    Alg. 5 : OEIS A007310 "Numbers congruent to 1 or 5 mod 6."
    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 :

    Alg. 6 : OEIS A007775 "Numbers not divisible by 2, 3 or 5."
    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.

    Alg. 7 (equivalent to Algorithm 6)
    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 W2=[2], and Algorithm 5 into the wheel W3=[2,4]. ℕ can even be created with W1=[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.

    Alg. 8 (equivalent to Algorithm 7)
    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(", ")+" ...]";
    

    From pre-sieving to wheel generation

    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 W1. One can even start from 0:

    Example 1 : Some wheels for Algorithm 8
    0+1 = 1 : W1 = [ 1 ];
    1+1 = 2 : W2 = [ 2 ];
    2+1 = 3 : W3 = [ 4, 2 ];
    4+1 = 5 : W5 = [ 6, 4, 2, 4, 2, 4, 6, 2 ];
       OEIS A145011 "First differences of A007775." (repeated infinitely)
    6+1 = 7 : W7 = [ 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).

    Properties of the wheels

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

    → 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).

    → In other words : W1, W2, W3, W5 and others are well studied and their primorial sizes are well defined (see below).

    → 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 :

    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#).

    Create a new wheel in 3 easy steps

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

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

    Alg. 9
    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.

    Alg. 10 (equiv. Algorithm 9)
    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.

    Alg. 11 Like Alg. 3 ("The prime numbers.") but differently.
    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.

    Stephen Maddox's observations

    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 W5 into W7 creates the temporary W':

    Example 4 : Unmerged W7
    W' = (W5[0]+1) × W5
       = 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 W7 appear there :

    Example 5 : Unmerged W7 (merge spots highlighted)
    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 W5 and matches Euler's phi formula.

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

    Example 6 : Accumulated gaps between merges to create W7 (the symmetry center is highlighted)
    6 => moved to the last line
    4 + 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 :

    Example 7 : direct relationship between W5 and W7
      [ 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 p2 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.

    Alg. 12 Modified Alg. 11 with more determinism (changes highlighted).
    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.

    The property of symmetry

    We have already seen that starting with W2, 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,
    Wu3 = p' × W2 = 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 :

    Alg. 12-2 Alg. 12 that displays the symmetry point of the 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 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;
    
    Example 8 : Value of the middle of the wheels
    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 W3, 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 W1 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...




    References

    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)).

    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

    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.

     

    Thanks

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