Mirror symmetry in distances of remaining numbers of Eratosthenes-sieve

77 Views Asked by At

Trying my first steps in Python I found an interesting phenomenon when I tried Eratosthenes sieve. Especially I looked for the distances between the remaining numbers. For example, if you already have the primes [2,3,5] the remaining numbers of an E-sieve are (1) 7 11 13 17 19 23 29 31 37 41 43 47 49 53 57 61 67 71 73 77 79 83 89 91 ...

  • So distances have a repeating pattern 6 4 2 4 2 4 6 2
    which I want to write a bit differently 6 4 2 <- 4 -> 2 4 6 // 2
  • to see the specials remove the always existing 2 on the last position
    then the other numbers have a mirror symmetry
known primes remaining numbers pattern between length of pattern
2 (1) 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 ... <- -> // 2 1
2, 3 (1) 5 7 11 13 17 19 23 25 29 31 ... <- 4 -> // 2 2
2, 3, 5 (1) 7 11 13 17 19 23 29 31 ... 6 4 2 <- 4 -> 2 4 6 // 2 8
2, 3, 5, 7 (1) 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 121 127 131 137 139 143 149 151 157 163 167 169 173 179 181 187 191 193 197 199 209 211 ... 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 48

My question for that I have yet not found answers:

  • is this a known pattern?
  • is there any literature about this?
  • have I made a mistake in my thoughts about this?

To understand better what I mean I wrote a piece of code (it's here only a non-optimized example - for speed I already have a better variant)

Nevertheless: this is only a very theoretical way to compute primes, the lists become very long - too long for any practical use. The only thing I see is to use the lists of patterns to step to the next number - so the amount of numbers can be reduced, which has to be tested with other methods.

Maybe the ending 2 of each pattern gives a hint for prime twins. The growing maximum number in each pattern is also a hint for the growing distances between subsequent primes in regions of bigger numbers.

# -*- coding: utf-8 -*-
"""
compute follow-up primes
based on distances
of remaining numbers
in Eratosthenes sieve
"""

import functools as FT
import itertools as IT
import operator as OP


def show(C:str, Z:list) -> None:
    # Where we are - list the current state
    LB = 16  # linebreak after LB numbers to eas readability
    print(C)
    if len(Z):
        for u, z in enumerate(Z):
            print(f'{z:>6}', end='')
            if ((u+1) % LB) == 0:
                print()
        else:
            if ((u+1) % LB) != 0:
                print()
    else:
        print('empty')

def check_list(J:list) -> bool:
    # the interesting part here !!!
    # symmetry of distance list = here called jumper
    b = True
    # 2               <--> <> ++ 2
    #
    # 4 2             <--> < 4 > ++ 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 <-->
    #                          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
    #
    # check last element is always a 2
    b &= (J[-1] == 2)
    # check without the last element list has mirror symmetry
    h = (len(J) // 2) - 1  # here middle of list
    b &= (J[0:h] == J[-2:h:-1])
    return b

def main() -> None:
    # List of primes to be added in each round
    primes = []
    # distances of remaining numbers in E-sieve,
    # 1 means that at the start every number is still available
    jumper = [1]
    #
    # primes = [2]        jumper = [                     2]
    # primes = [2,3]      jumper = [4,                   2]
    # primes = [2,3,5]    jumper = [6,4,2,  4,   2,4,6,  2]
    # primes = [2,3,5,7]  jumper = [10,2,4, ... 4,2,10,  2]
    #
    show('current known primes', primes)
    see_more = True  # to see some additional output
    #
    while True:
        # follow-up prime is based on the first jumper number added by 1
        if see_more: show('start-up jumper list', jumper)
        if see_more: print(len(jumper), jumper[:8])
        print('\n', p := 1 + jumper[0], ' <-- next prime number \n')
        # put it on to list of primes
        primes.append(p)

        # To build next list we need to repeat the current jumper-list p times
        L = jumper * p
        if see_more: show('repeated jumpers', L)
        # product of primes == sum of jumpers ! LCM = border for repeated pattern
        P = FT.reduce(OP.mul, primes, 1)
        Q = FT.reduce(OP.add, L, 0)
        assert P == Q

        # Starting with 1 adding the jumpers will meet the following numbers
        K = [n for n in IT.accumulate(L, OP.add, initial=1) if n > 1]
        if see_more: show('this will meet on' ,K)

        # so we still have to handle the following numbers or adding steps
        N = [n*p for n in IT.accumulate(jumper, OP.add, initial=1) if n*p <= P]
        if see_more: show('need to strike out', N)

        # collecting together where we meet strikeouts
        J = []
        jj = 0
        kk = 1
        for (j, k) in zip(L, K):
            jj += j  # Remember the former jumper if we meet a strike-out
            kk += j
            if kk not in N:
                J.append(jj)
                jj = 0  # reset remembering
            else:
                J.append('x')
        # temporary part only to see what and where happens on striking out numbers
        if see_more: show('temporary jumpers', J)
        while 'x' in J:
            J.remove('x')
        #
        show('current known primes', primes)
        if see_more: show('resulting jumper list', J)
        assert check_list(J)
        jumper = J
        #
        if p >= 11: break
        # try bigger numbers - caution length of list grows rapidly
        # LEN jumper = product_over(p-1) <--> (2-1)(3-1)(5-1)(7-1)...
if __name__ == "__main__":
    main()