I have been working on a problem in number theory for some time, however I am not a mathematician so please bear with me. I have appealed to mathematicians and programmers, but all I get is silence. I feel that this community will be totally willing to give feedback / destroy any weakness or foolishness on my part.
Anyway, sieves traditionally operate sequentially by finding a number and then striking multiples of that number, finding the next surviving number, striking multiples of it, so on and so forth. This of course treats the continuum of primes as a single sequence.
I noticed that the primes (excluding 2, 3 and 5) could be subdivided into 24 classes, as follows (taken from Sloane's A00040: "Reading the primes (excluding 2,3,5) mod 90 divides them into 24 classes, which are described by A181732, A195993, A198382, A196000, A201804, A196007, A201734, A201739, A201819, A201816, A201817, A201818, A202104, A201820, A201822, A201101, A202113, A202105, A202110, A202112, A202129, A202114, A202115 and A202116."
Without going into too much detail, those are "digital root and last digit preserving sequences."
At any rate, once the primes are thus subdivided it becomes trivial to remove composites, such that there is no "internal state dependency" which mean, in effect, that we can perform the operations of striking off the composites out of order. There is no discovery process, rather we can define all composites with a closed-form expression. I hope I am using that correctly.
Anyway, words are pointless. What you should insist upon is code. So, we have the following sequence: A255491 Numbers n such that 90*n+1 is composite.
And the following code to produce the sequence:
#!/usr/local/env python #python 2.7
import sys
import csv
import time
import subprocess
dump = open("composite1.csv", "w")
new_test = 40000
def dr1_ld1_91_91(x):
y = 90*(x*x) + 2*x
if y > new_test:
return
#print "91", y
dump.write(str(y) + "\n")
for n in range(1, new_test):
new_y = y+((91+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
def dr1_ld1_19_19(x):
y = 90*(x*x) - 142*x + 56
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+ ((19+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
def dr1_ld1_37_73(x):
y = 90*(x*x) - 70*x + 10
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((37+(90*(x-1)))*n)
new2_y = y+((73+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_11_41(x):
y = 90*(x*x) - 128*x + 43
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((11+(90*(x-1)))*n)
new2_y = y+((41+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_29_59(x):
y = 90*(x*x) - 92*x + 21
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((29+(90*(x-1)))*n)
new2_y = y+((59+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_47_23(x):
y = 90*(x*x) - 110*x + 32
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((23+(90*(x-1)))*n)
new2_y = y+((47+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_77_83(x):
y = 90*(x*x) - 20*x + 1
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((77+(90*(x-1)))*n)
new2_y = y+((83+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_7_13(x):
y = 90*(x*x) - 160*x + 71
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((7+(90*(x-1)))*n)
new2_y = y+((13+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_31_61(x):
y = 90*(x*x) - 88*x + 19
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((31+(90*(x-1)))*n)
new2_y = y+((61+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_49_79(x):
y = 90*(x*x) - 52*x + 5
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((49+(90*(x-1)))*n)
new2_y = y+((79+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_43_67(x):
y = 90*(x*x) - 70*x + 12
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((43+(90*(x-1)))*n)
new2_y = y+((67+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_17_53(x):
y = 90*(x*x) - 110*x + 30
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((17+(90*(x-1)))*n)
new2_y = y+((53+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
if new2_y < new_test:
dump.write(str(new2_y) + "\n")
def dr1_ld1_71_71(x):
y = 90*(x*x) - 38*x + 4
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((71+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
def dr1_ld1_89_89(x):
y = 90*(x*x) - 2*x
if y > new_test:
return
dump.write(str(y) + "\n")
for n in range (1, new_test):
new_y = y+((89+(90*(x-1)))*n)
if new_y < new_test:
dump.write(str(new_y) + "\n")
for x in xrange(1, 150): #22
dr1_ld1_7_13(x) #1 @xrange(x) = 22, y = 1814
dr1_ld1_19_19(x) #4
dr1_ld1_11_41(x) #5
dr1_ld1_17_53(x) #10
dr1_ld1_47_23(x) #12
dr1_ld1_29_59(x) #19
dr1_ld1_31_61(x) #21
dr1_ld1_37_73(x) #30
dr1_ld1_43_67(x) #32
dr1_ld1_49_79(x) #43
dr1_ld1_71_71(x) #56
dr1_ld1_77_83(x) #71
dr1_ld1_89_89(x) #88
dr1_ld1_91_91(x) #92
def bash_command(cmd):
subprocess.Popen(cmd, shell=True)
bash_command('sort -n composite1.csv -o composite2.csv')
time.sleep(1.2) #make sure subprocess has finished
z=1000
f=open("composite2.csv")
for i in range(z):
line=f.next().strip()
print line
#print "not prime", line
f.close()
proceed = raw_input("shall we proceed to print the next 10,000 primes?")
if proceed == "yes":
pass
if proceed == "no":
#execfile("ElderSieve.py")
quit("goodbye")
#run this code to compare to https://oeis.org/A181732/b181732.txt
with open("composite2.csv") as f:
rd=f.readlines()
x=[t.strip("\n") for t in rd]
for i in range(0, 37188):
if str(i) not in x:
print ("{} is prime".format(i))
So as you can see there are 14 functions that print numbers, and if you take these numbers, multiply them by 90 and add 1, you will generate a composite in base 10. By the same token, any number not printed by the functions can be multiplied by 90 and then add 1 and you will have a prime number. The reasons for why this is so are related to the algebraic laws of composite generation within sequences that preserve the digital root and last digit. So this is a digital root 1 and last digit 1 preserving sequence generator.
Thank you so much for your time!
You can check out all the code at github: https://github.com/superobserver/elder-sieve