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