Print    Contact Us

Recursion on the cycle of gaps

The cycle of gaps

Let Pk be the product of the first k primes. After k stages of Eratosthenes sieve, the possible primes are the generators of Z mod Pk plus their images under repeated addition of Pk. There is a cycle of gaps among these possible primes. The cycle has Q elements which sum up to Pk.

After two stages of Eratosthenes sieve, we have removed multiples of 2 and 3 as possible primes. The cycle of gaps G(3#) is the constellation 42.

In the third stage of Eratosthenes sieve, we remove multiples of 5 as possible primes. The cycle of gaps G(5#) is the constellation 64242462.

The recursion

The recursion which generates G(Pk#) from G(Pk-1#) consists of three steps:

  1. Next prime: pk is one more than the first gap in G(Pk-1#);
  2. Concatenation: concatenate pk copies of G(Pk-1#);
  3. Select additions: add pairs of gaps as indicated by the elementwise product pk*G(Pk-1#).

Example

G(3#) = 42. Following the steps of the recursion, we find that the next prime is 4+1 = 5. We concatenate 5 copies of G(3#):

 4  2  4  2  4  2  4  2  4  2 

The element-wise product 5 * G(3#) = 20,10. We introduce commas here to set apart the two-digit entries. The additions work as follows. We add together the first two gaps (removing the new prime). Then we advance through the concatenated gaps from addition to addition, with the running sums between additions equal to the element-wise product:

    G(5#) = 4+2 4 2 4 2 4 2+4 2 
          = 6 4 2 4 2 4 6 2
    

Note that the gaps between the two additions sum to 20, and remembering that this is a cycle, the sum from the second addition around to the first addition again is 10.

    G(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 
          = 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

Note that the gaps between the additions sum to 7*G(5#)=42,28,14,28,14,28,42,14, respectively.




This page gives an overview of the recursion. This research is described in detail in this manuscript.

You can visualize the recursion using our online javascript tool and gap cycle data is available on the computational results page.