Prime Number Sieve/Sieve of Eratosthenes
A mathematical model using formula analysis of prime numbers...
 |
SiteMap of SciRealm | About John | John's Resume/C.V./Bio | Send email to John
John's Science, Math, Philosophy Stuff:
The Science Realm: John's Virtual Sci-Tech Universe | 4-Vectors | Ambigrams | Antipodes | Covert Ops Fragments | Cyrillic Projector | Forced Induction (Sums Of Powers Of Integers) | Fractal Tree | Frontiers | IFS Fractals (Assembly) | IFS Fractals (Javascript) | JavaScript Graphics | Kid Science | Kryptos | Philosophy | Photography | Physics-Planck Constant Measurement Via LEDs | Prime Sieve | QM from SR | QM from SR-Simple RoadMap | QM from SR-Simple RoadMap (PDF) | SR 4-Vector & Tensor Calculator |Quantum Phase | Quotes | RuneQuest Cipher Challenge | Secret Codes & Ciphers | Scientific Calculator (complex capable) | Science+Math | Sci-Pan Pantheist Poems | Stereograms | SuperMagicSqr4x4 |Turkish Grammar |Melike Wilson Art
Site last modified: 2021-Aug |
Welcome to Relativistic Quantum Reality: Virtual worlds of imaginary particles: The dreams stuff is made of: Life, the eternal ghost in the machine...
This site is dedicated to the quest for knowledge and wisdom, through science, mathematics, philosophy, invention, and technology.
May the treasures buried herein spark the fires of imagination like the twinkling jewels of celestial light crowning the midnight sky...
Quantum Mechanics is derivable from Special Relativity
See SRQM - QM from SR - Simple RoadMap (.html)
See SRQM - QM from SR - Simple RoadMap (.pdf)
See SRQM - Online SR 4-Vector & Tensor Calculator
See Online Complex-capable RPN Scientific Calculator
***Learn, Discover, Explore***
|
|
Note: This work is not finished, but if you notice errors or have comments, please
let me know.
Prime Number Sieve/Sieve of Eratosthenes
The Prime Sieve is a constructive method
or algorithm for finding prime numbers. This document will analyze the method in some
detail, hopefully adding to our mathematical knowledge.
We begin with the assumption that the form of the prime #'s is n, where n is any whole
number.
Let us make a list of the first few non-negative integers:
00, 01, 02, 03, 04, 05, 06, 07,
08, 09,
10, 11, 12, 13, 14, 15, 16, 17,
18, 19,
20, 21, 22, 23, 24, 25, 26, 27,
28, 29,
30, 31, 32, 33, 34, 35, 36, 37,
38, 39,
40, 41, 42, 43, 44, 45, 46, 47,
48, 49,
50, 51, 52, 53, 54, 55, 56, 57,
58, 59,
60, 61, 62, 63, 64, 65, 66, 67,
68, 69,
70, 71, 72, 73, 74, 75, 76, 77,
78, 79,
80, 81, 82, 83, 84, 85, 86, 87,
88, 89,
90, 91, 92, 93, 94, 95, 96, 97,
98, 99,
...
This list will contain all of the primes from 0 to 99, but also all of the non-primes, or
composite numbers.
The way the usual sieve method works is to find the lowest prime number, and then cross
out all multiples of it in the remainder of the list. So, for instance, if we start with
prime 2, we cross out 4,6,8,10,12,... etc. The next lowest prime is 3, so we cross out
6,9,12,... etc. Notice that some of the numbers were already crossed out, any that were
already multiples of 2, such as 6 and 12. Anyway, you now continue along in this fashion,
until the only numbers left on the list are the prime numbers.
In this analysis, I instead attempt to find the mathematical form of the prime numbers
after each application of a particular sieve. Before we start, we simply assume that the
primes are of form n, where n is any non-negative integer. We then apply the first sieve,
or Sieve-1 in this notation. Now the case of number 1 is kind of special, as it is
kind of like a prime, but nowadays it is considered to be neither prime nor
composite. However, in my analysis, it works just like a regular prime based on the
patterns. Each sieve gives a mathematical form and a region of applicability. So,
Sieve-1 will find primes >1 and <4 (6), and has the mathematical form of [n1],
where n1 is an integer. Thus, it finds the confirmed primes 2,3,
and can extend to find confirmed prime 5. Since 2 is the next lowest found prime, we then
run Sieve-2. It will find primes >2 and <9 (15), and has the mathematical form of [2n2+1],
where n2 is an integer. Thus, it finds the confirmed primes 3,5,7, and
can extend to find confirmed primes 11,13. How these ranges are found will be explained
later.
To find the lower assured bound, each Sieve-N assumes N is prime, and attempts to find
primes>N by crossing out composite #'s that are multiples of N, or k*N, for integer
k>1, and leaving behind the primes>N. One might think that N itself should be
including in the range of Sieve-N, since it is prime, but the formula representation of
Sieve-N excludes this. However, the prime N is not lost because it was included and
confirmed in the previous Sieve.
To find the upper assured bound, we have to find the minimum composite number which is not
crossed out by Sieve-N. This first occurs at NextPrime[N]*NextPrime[N]. The reason
for this is as follows: Let (c =a*b) be the smallest composite number not crossed
out by Sieve-N or before. This means that c (and a and b) cannot have any prime factors of
N or smaller, as these would have been crossed out already. The next smallest number would
be c=a*b, where a=NextPrime[N] and b=NextPrime[N]. Thus, the 1st failure always occurs at
c=
(NextPrime[N])*(NextPrime[N])=NextPrime[N]2.
However, the maximum assured range can be extended a bit further, because the next
smallest composite always has the same form, which is where the 2nd failure happens. It
occurs at k=(NextPrime[N])*(NextPrime[NextPrime[N]]).Now,
there will be some primes further out, but we are not sure which numbers are the primes
until more sieves are applied. The third failure cannot be pinned down so easily.
Thus, we will take the upper assured prime value as k=(NextPrime[N])*(NextPrime[NextPrime[N]]),
and noting that there is one composite number within the assured range that must
be excluded, which is
c=(NextPrime[N])*(NextPrime[N])=NextPrime[N]2
During the sieve procedure, at any given step, there is a pattern to the remaining
numbers. Once the multiples of 2 are crossed out, the remaining numbers are spaced
at intervals of 2. Thus, there is a repeat distance of 2. Once the multiples
of 3 are crossed out, the pattern becomes intervals of 2,4,2,4,... This makes two
branches with different starting points, each with a repeat distance of 6.
Note on coloring:
I use purple for
"Prime-1".
I use green for new assured primes.
I use blue for the extended assured primes.
I use yellow for old, already found primes.
I use red for sieve
failed composites.
I use dark gray for composites.
Now then, let's get started...
Apply Sieve-1:
Finds: primes>1
The repeat distance is: 1
Possible forms/branches is: 1
Includes: All whole numbers, which may be zero or prime or composite
Excludes: All non-whole numbers, i.e. fractions, irrationals, etc.
1st failure at: 4=2*2=22
2nd failure at: 6=2*3
Assured prime range: 1 < primes < 6
|
Failures:
|
2*2=4
|
2*2*2=8
|
|
|
2*3=6
|
3*3=9
|
|
|
2*5=10
|
|
|
#
|
Mathematical Form
|
c1 values (0..0)
|
Old/New/Extended
Primes
|
Bad/Failed
|
|
1
|
1 < [n1+c1]
< 22 = 4 (6)
which simplifies to:
1 < [n1] < 22 = 4 (6)
|
0
|
1,2,3,5,7?
|
4,6
|
00, 01,
[02, 03,
04,
05] 06,
07, 08, 09,
10, 11, 12, 13, 14, 15, 16, 17,
18, 19,
20, 21, 22, 23, 24, 25, 26, 27,
28, 29,
30, 31, 32, 33, 34, 35, 36, 37,
38, 39,
40, 41, 42, 43, 44, 45, 46, 47,
48, 49,
50, 51, 52, 53, 54, 55, 56, 57,
58, 59,
...
Next confirmed prime is 2...
We need [n1] mod 2 <> 0
Try (n1=2n2+c2)
[2n2+c2] mod 2 <> 0
which simplifies to:
[c2] mod 2 <> 0
Solution is Complement[0] of (0..1), c2=1
Apply Sieve-2:
Finds: primes>2
The repeat distance is: 2
Possible forms/branches is: 1*(2-1)=1
Includes: All primes>2 and composites with prime factors>2
Excludes: All multiples of 2, [2n2+0]
1st failure at: 9=3*3=32
2nd failure at: 15=3*5
Assured prime range: 2 < primes < 15
|
Failures:
|
3*3=9
|
3*3*3=27
|
|
|
3*5=15
|
5*5=25
|
|
|
3*7=21
|
|
|
#
|
Mathematical Form
|
c2 values (0..1)
|
Old/New/Extended
Primes
|
Bad/Failed
|
|
1
|
2 < [2n2+c2]
< 32 = 9 (15)
which simplifies to:
2 < [2n2+1] < 32 = 9 (15)
|
Complement[0]
=1
|
x,
1,3,5,7,,11,13,,17?,19?,
|
9,15
|
00,
01,
02, [03,
04, 05,
06, 07,
08, 09,
10, 11,
12, 13]
14, 15,
16, 17, 18,
19,
20, 21, 22,
23, 24, 25, 26,
27, 28, 29,
30, 31, 32,
33, 34, 35, 36,
37, 38, 39,
40, 41, 42,
43, 44, 45, 46,
47, 48, 49,
50, 51, 52,
53, 54, 55, 56,
57, 58, 59,
60, 61, 62,
63, 64, 65, 66,
67, 68, 69,
...
Next confirmed prime is 3...
We need [2n2+1] mod 3 <> 0
Try (n2=3n3+c3)
[6n3+2c3+1] mod 3 <> 0
which simplifies to:
[2c3+1] mod 3 <> 0
Solution is Complement[1] of (0..2), c3=0,2
Apply Sieve-3:
Finds: primes>3
The repeat distance is: 2*3=6
Possible forms/branches is: 1*(3-1)=2
Includes: All primes>3 and composites with prime factors>3
Excludes: All multiples of 3 not already excluded, [6n3+3]
1st failure at: 25=5*5=52
2nd failure at: 35=5*7
Assured prime range: 3 < primes < 35
|
Failures:
|
5*5=25
|
|
|
|
5*7=35
|
7*7=49
|
|
|
5*11=55
|
|
|
#
|
Mathematical Form
|
c3 values (0..2)
|
Old/New/Extended
Primes
|
Bad/Failed
|
|
1
|
3 < [6n3+2c3+1]
< 52 = 25 (35)
which simplifies to:
3 < [6n3+1] < 52 = 25 (35)
&
3 < [6n3+5] < 52 = 25 (35)
|
Complement[1]
=0,2
|
1,7,13,19,,31
x,
5,11,17,23,29
|
25
35
|
00,
01,
02, 03,
04, [05,
06, 07,
08, 09,
10, 11,
12, 13,
14, 15,
16, 17,
18, 19,
20, 21,
22, 23,
24, 25,
26, 27,
28, 29,
30, 31]
32, 33,
34, 35,
36, 37, 38,
39,
40, 41, 42,
43, 44, 45,
46, 47, 48,
49,
50, 51,
52, 53, 54,
55, 56, 57,
58, 59,
60, 61, 62,
63, 64,
65, 66, 67, 68,
69,
70, 71, 72,
73, 74, 75,
76, 77, 78,
79,
80, 81,
82, 83, 84,
85, 86, 87,
88, 89,
...
Alternate single branch form: [3n-2+(1+(-1)n)/2] for n>0
Next confirmed prime is 5...
We need [6n3+2c3+1] mod 5 <> 0, for the cases of
c3=0,2
Try (n3=5n5+c5)
For the case of c3=0
[30n5+6c5+1] mod 5 <> 0
which simplifies to:
[c5+1] mod 5 <> 0
Solution is Complement[4] of (0..4)
c5=0,1,2,3
|
For the case of c3=2
[30n5+6c5+5] mod 5 <> 0
which simplifies to:
[c5+0] mod 5 <> 0
Solution is Complement[0] of (0..4)
c5=1,2,3,4
|
Apply Sieve-5:
Finds: primes>5
The repeat distance is: 2*3*5=30
Possible forms/branches is: 2*(5-1)=8
Includes: All primes>5 and composites with prime factors>5
Excludes: All multiples of 5 not already excluded, i.e. [30n5+6*4+1]
and [30n5+6*0+5]
1st failure at: 49=7*7=72
2nd failure at: 77=7*11
Assured prime range: 5 < primes < 77
|
Failures:
|
7*7=49
|
|
|
|
7*11=77
|
11*11=121
|
|
|
7*13=91
|
|
|
|
7*17=119
|
|
|
#
|
Mathematical Form
|
c5 values (0..4)
|
Old/New/Extended
Primes
|
Bad/Failed
|
|
1
|
5 < [30n5+6c5+1]
< 72 = 49 (77)
|
Complement[4]
=0,1,2,3
|
1,31,61
7,37,67,97?,127?,157?
13,43,73,103?
19
x,
|
91
187
133
49
|
|
2
|
5 < [30n5+6c5+5]
< 72 = 49
|
Complement[0]
=1,2,3,4
|
x,
11,41,71,101?,131?
17,47
23,53,83?,113?
29,59,89?
|
161
77
143
119
|
00, 01,
02, 03,
04, 05,
06, [07,
08, 09,
10, 11,
12, 13,
14, 15, 16,
17, 18,
19,
20, 21, 22,
23, 24,
25, 26,
27, 28, 29,
30, 31,
32, 33, 34,
35, 36,
37, 38,
39,
40, 41,
42, 43,
44, 45, 46,
47, 48,
49,
50, 51, 52,
53, 54,
55, 56,
57, 58, 59,
60, 61,
62, 63, 64,
65, 66,
67, 68,
69,
70, 71,
72, 73]
74, 75, 76,
77,
78, 79,
80, 81, 82,
83, 84, 85,
86, 87, 88,
89,
90, 91, 92,
93, 94, 95,
96, 97, 98, 99,
100,101,102,103,104,105,106,107,108,109,
110,111,112,113,114,115,116,117,118,119,
120,121,122,123,124,125,126,127,128,129,
...
Next confirmed prime is 7...
We need [30n5+6c5+1] mod 7 <> 0, for the cases
of c5=0,1,2,3
We need [30n5+6c5+5] mod 7 <> 0, for the cases
of c5=1,2,3,4
Try (n5=7n7+c7)
For the case of [30n5+6c5+1] and
c5=0
[210n7+30c7+1] mod 7 <> 0
which simplifies to:
[2c7+1] mod 7 <> 0
Solution is Complement[3] of (0..6)
c7=0,1,2,4,5,6
|
For the case of [30n5+6c5+5] and
c5=1
[210n7+30c7+11] mod 7 <> 0
which simplifies to:
[2c7+4] mod 7 <> 0
Solution is Complement[5] of (0..6)
c7=0,1,2,3,4,6
|
For the case of [30n5+6c5+1] and
c5=1
[210n7+30c7+7] mod 7 <> 0
which simplifies to:
[2c7+0] mod 7 <> 0
Solution is Complement[0] of (0..6)
c7=1,2,3,4,5,6
|
For the case of [30n5+6c5+5] and
c5=2
[210n7+30c7+17] mod 7 <> 0
which simplifies to:
[2c7+3] mod 7 <> 0
Solution is Complement[2] of (0..6)
c7=0,1,3,4,5,6
|
For the case of [30n5+6c5+1] and
c5=2
[210n7+30c7+13] mod 7 <> 0
which simplifies to:
[2c7+6] mod 7 <> 0
Solution is Complement[4] of (0..6)
c7=0,1,2,3,5,6
|
For the case of [30n5+6c5+5] and
c5=3
[210n7+30c7+23] mod 7 <> 0
which simplifies to:
[2c7+2] mod 7 <> 0
Solution is Complement[6] of (0..6)
c7=0,1,2,3,4,5
|
For the case of [30n5+6c5+1] and
c5=3
[210n7+30c7+19] mod 7 <> 0
which simplifies to:
[2c7+5] mod 7 <> 0
Solution is Complement[1] of (0..6)
c7=0,2,3,4,5,6
|
For the case of [30n5+6c5+5] and
c5=4
[210n7+30c7+29] mod 7 <> 0
which simplifies to:
[2c7+1] mod 7 <> 0
Solution is Complement[3] of (0..6)
c7=0,1,2,4,5,6
|
Apply Sieve-7:
Finds: primes>7
The repeat distance is: 2*3*5*7=210
Possible forms/branches is: 8*(7-1)=48
Includes: All primes>7 and composites with prime factors>7
Excludes: All multiples of 7 not already excluded,
[210n7+30*3+1] and [210n7+30*0+7] and [210n7+30*5+11]
and [210n7+30*4+13] and
[210n7+30*2+17] and [210n7+30*1+19] and [210n7+30*6+23]
and [210n7+30*3+29]
1st failure at: 121=11*11=112
2nd failure at: 143=11*13
Assured prime range: 7 < primes < 143
|
Failures:
|
11*11=121
|
|
|
|
11*13=143
|
13*13=169
|
|
|
11*17=187
|
13*17=221
|
|
|
11*19=209
|
|
|
#
|
Mathematical Form
|
c7 values (0..6)
|
Old/New/Extended/Bad
Primes
|
|
1
|
7 < [210n7+30c7+1]
< 112 = 121 (143)
|
Complement[3]
=0,1,2,4,5,6
|
1,31,61,x,121,151?,181?/211?,241?,271?,301?
|
|
2
|
7 < [210n7+30c7+7]
< 112 = 121
|
Complement[0]
=1,2,3,4,5,6
|
x,37,67,97,127,157?,187?,/
|
|
3
|
7 < [210n7+30c7+11]
< 112 = 121
|
Complement[5]
=0,1,2,3,4,6
|
11,41,71,101,131,x,191?,/221?
|
|
4
|
7 < [210n7+30c7+13]
< 112 = 121
|
Complement[4]
=0,1,2,3,5,6
|
13,43,73,103,x,163?,193?,/223?,253?
|
|
5
|
7 < [210n7+30c7+17]
< 112 = 121
|
Complement[2]
=0,1,3,4,5,6
|
17,47,x,107,137,167?,197?,/227?,257?,287?
|
|
6
|
7 < [210n7+30c7+19]
< 112 = 121
|
Complement[1]
=0,2,3,4,5,6
|
19,x,79,109,139,169,199?/
|
|
7
|
7 < [210n7+30c7+23]
< 112 = 121
|
Complement[6]
=0,1,2,3,4,5
|
23,53,83,113,143,173?,x,/
|
|
8
|
7 < [210n7+30c7+29]
< 112 = 121
|
Complement[3]
=0,1,2,4,5,6
|
29,59,89,x,149?,179?,209?/
|
00, 01,
02, 03,
04, 05,
06, 07,
08, 09,
10, [11,
12, 13,
14, 15, 16,
17, 18,
19,
20, 21, 22,
23, 24,
25, 26,
27, 28, 29,
30, 31,
32, 33, 34,
35, 36,
37, 38,
39,
40, 41,
42, 43,
44, 45, 46,
47, 48,
49,
50, 51, 52,
53, 54,
55, 56,
57, 58, 59,
60, 61,
62, 63, 64,
65, 66,
67, 68,
69,
70, 71,
72, 73,
74, 75, 76,
77, 78,
79,
80, 81, 82,
83, 84,
85, 86,
87, 88, 89,
90, 91,
92, 93, 94,
95, 96,
97, 98,
99,
100,101,102,103,104,105,106,107,108,109,
110,111,112,113,114,115,116,117,118,119,
120,121,122,123,124,125,126,127,128,129,
130,131,132,133,134,135,136,137,138,139]
140,141,142,143,144,145,146,147,148,149,
150,151,152,153,154,155,156,157,158,159,
160,161,162,163,164,165,166,167,168,169,
170,171,172,173,174,175,176,177,178,179,
180,181,182,183,184,185,186,187,188,189,
190,191,192,193,194,195,196,197,198,199,
...
Next confirmed prime is 11...
We need [210n7+30c7+k]
mod 11 <> 0, for the cases of c7=various
Try (n7=11n11+c11)
Apply Sieve-11:
Finds: primes>11
The repeat distance is: 2*3*5*7*11=2310
Possible forms/branches is: 48*(11-1)=480
Includes: All primes>11 and composites with prime factors>11
Excludes: All multiples of 11 not already excluded, 48 branches
1st failure at: 169=13*13=132
2nd failure at: 221=13*17
Assured prime range: 11 < primes < 221
|
Failures:
|
13*13=169
|
|
|
|
13*17=221
|
17*17=289
|
|
|
13*19=247
|
17*19=323
|
|
|
13*23=299
|
|
|
#
|
Mathematical Form
|
c11 values (0..10)
|
Old/New/Extended/Bad
Primes
|
|
01
|
11 < [2310n11+210c11+1]
< 132 = 169 (221)
|
Comp[10]
|
1,211,421?,...
|
|
02
|
11 < [2310n11+210c11+11]
< 132 = 169
|
Comp[0]
|
x,221,431?,...
|
|
03
|
11 < [2310n11+210c11+13]
< 132 = 169
|
Comp[9]
|
13,223?,...
|
|
04
|
11 < [2310n11+210c11+17]
< 132 = 169
|
Comp[5]
|
17,227?,...
|
|
05
|
11 < [2310n11+210c11+19]
< 132 = 169
|
Comp[3]
|
19,229?,...
|
|
06
|
11 < [2310n11+210c11+23]
< 132 = 169
|
Comp[10]
|
23,233?,...
|
|
07
|
11 < [2310n11+210c11+29]
< 132 = 169
|
Comp[4]
|
29,239?,...
|
|
08
|
11 < [2310n11+210c11+31]
< 132 = 169
|
Comp[2]
|
31,241?,...
|
|
09
|
11 < [2310n11+210c11+37]
< 132 = 169
|
Comp[7]
|
37,247?,...
|
|
10
|
11 < [2310n11+210c11+41]
< 132 = 169
|
Comp[3]
|
41,251?,...
|
|
11
|
11 < [2310n11+210c11+43]
< 132 = 169
|
Comp[1]
|
43,253,...
|
|
12
|
11 < [2310n11+210c11+47]
< 132 = 169
|
Comp[8]
|
47,257?,...
|
|
13
|
11 < [2310n11+210c11+53]
< 132 = 169
|
Comp[2]
|
53,263?,...
|
|
14
|
11 < [2310n11+210c11+59]
< 132 = 169
|
Comp[7]
|
59,269?,...
|
|
15
|
11 < [2310n11+210c11+61]
< 132 = 169
|
Comp[5]
|
61,271?,...
|
|
16
|
11 < [2310n11+210c11+67]
< 132 = 169
|
Comp[10]
|
67,277?,...
|
|
17
|
11 < [2310n11+210c11+71]
< 132 = 169
|
Comp[6]
|
71,281?,...
|
|
18
|
11 < [2310n11+210c11+73]
< 132 = 169
|
Comp[4]
|
73,283?,...
|
|
19
|
11 < [2310n11+210c11+79]
< 132 = 169
|
Comp[9]
|
79,289?,...
|
|
20
|
11 < [2310n11+210c11+83]
< 132 = 169
|
Comp[5]
|
83,293?,...
|
|
21
|
11 < [2310n11+210c11+89]
< 132 = 169
|
Comp[10]
|
89,299?,...
|
|
22
|
11 < [2310n11+210c11+97]
< 132 = 169
|
Comp[2]
|
97,307?,...
|
|
23
|
11 < [2310n11+210c11+101]
< 132 = 169
|
Comp[9]
|
101,311?,...
|
|
24
|
11 < [2310n11+210c11+103]
< 132 = 169
|
Comp[7]
|
103,313?,...
|
|
25
|
11 < [2310n11+210c11+107]
< 132 = 169
|
Comp[3]
|
107,317?,...
|
|
26
|
11 < [2310n11+210c11+109]
< 132 = 169
|
Comp[1]
|
109,319,...
|
|
27
|
11 < [2310n11+210c11+113]
< 132 = 169
|
Comp[8]
|
113,323?,...
|
|
28
|
11 < [2310n11+210c11+121]
< 132 = 169
|
Comp[0]
|
x,331?,541?,...
|
|
29
|
11 < [2310n11+210c11+127]
< 132 = 169
|
Comp[5]
|
127,337?,...
|
|
30
|
11 < [2310n11+210c11+131]
< 132 = 169
|
Comp[1]
|
131,341,...
|
|
31
|
11 < [2310n11+210c11+137]
< 132 = 169
|
Comp[6]
|
137,347?,...
|
|
32
|
11 < [2310n11+210c11+139]
< 132 = 169
|
Comp[4]
|
139,349?,...
|
|
33
|
11 < [2310n11+210c11+143]
< 132 = 169
|
Comp[0]
|
x,353?,...
|
|
34
|
11 < [2310n11+210c11+149]
< 132 = 169
|
Comp[5]
|
149,359?,...
|
|
35
|
11 < [2310n11+210c11+151]
< 132 = 169
|
Comp[3]
|
151,361?,...
|
|
36
|
11 < [2310n11+210c11+157]
< 132 = 169
|
Comp[8]
|
157,367?,...
|
|
37
|
11 < [2310n11+210c11+163]
< 132 = 169
|
Comp[2]
|
163,373?,...
|
|
38
|
11 < [2310n11+210c11+167]
< 132 = 169
|
Comp[9]
|
167,377?,...
|
|
39
|
11 < [2310n11+210c11+169]
< 132 = 169
|
Comp[7]
|
169,379?,...
|
|
40
|
11 < [2310n11+210c11+173]
< 132 = 169
|
Comp[3]
|
173,383?,...
|
|
41
|
11 < [2310n11+210c11+179]
< 132 = 169
|
Comp[8]
|
179,389?,...
|
|
42
|
11 < [2310n11+210c11+181]
< 132 = 169
|
Comp[6]
|
181,391?,...
|
|
43
|
11 < [2310n11+210c11+187]
< 132 = 169
|
Comp[0]
|
x,397?,...
|
|
44
|
11 < [2310n11+210c11+191]
< 132 = 169
|
Comp[7]
|
191,401?,...
|
|
45
|
11 < [2310n11+210c11+193]
< 132 = 169
|
Comp[5]
|
193,403?,...
|
|
46
|
11 < [2310n11+210c11+197]
< 132 = 169
|
Comp[1]
|
197,407,...
|
|
47
|
11 < [2310n11+210c11+199]
< 132 = 169
|
Comp[10]
|
199,409?,...
|
|
48
|
11 < [2310n11+210c11+209]
< 132 = 169
|
Comp[0]
|
x,419?,...
|
00, 01,
02, 03,
04, 05,
06, 07,
08, 09,
10, 11,
12, [13,
14, 15, 16,
17, 18,
19,
20, 21, 22,
23, 24,
25, 26,
27, 28, 29,
30, 31,
32, 33, 34,
35, 36,
37, 38,
39,
40, 41,
42, 43,
44, 45, 46,
47, 48,
49,
50, 51, 52,
53, 54,
55, 56,
57, 58, 59,
60, 61,
62, 63, 64,
65, 66,
67, 68,
69,
70, 71,
72, 73,
74, 75, 76,
77, 78,
79,
80, 81, 82,
83, 84,
85, 86,
87, 88, 89,
90, 91,
92, 93, 94,
95, 96,
97, 98,
99,
100,101,102,103,104,105,106,107,108,109,
110,111,112,113,114,115,116,117,118,119,
120,121,122,123,124,125,126,127,128,129,
130,131,132,133,134,135,136,137,138,139,
140,141,142,143,144,145,146,147,148,149,
150,151,152,153,154,155,156,157,158,159,
160,161,162,163,164,165,166,167,168,169,
170,171,172,173,174,175,176,177,178,179,
180,181,182,183,184,185,186,187,188,189,
190,191,192,193,194,195,196,197,198,199,
200,201,202,203,204,205,206,207,208,209,
210,211]212,213,214,215,216,217,218,219,
220,221,222,223,224,225,226,227,228,229,
...
Next confirmed prime is 13...
We need [2310n11+210c11+k] mod 13 <> 0, for the
cases of c11=various
Try (n11=13n13+c13)
Apply Sieve-13:
Finds primes>13
The repeat distance is 2*3*5*7*11*13=30030
Possible forms/branches is 480*(13-1)=5760
Includes: All primes>13 and composites with prime factors>13
Excludes: All multiples of 13 not already excluded, 480 branches
1st failure at 289=17*17=172
2nd failure at 323=17*19
Assured prime range: 13 < primes < 323
|
Failures:
|
17*17=289
|
|
|
|
17*19=323
|
19*19=361
|
|
|
17*23=391
|
|
|
#
|
Mathematical Form
|
c13 values (0..12)
|
Old/New/Extended/Bad
Primes
|
|
01
|
13 < [30030n13+2310c13+1]
< 172 = 289 (323)
|
Comp[]
|
1,?
|
|
02
|
13 < [30030n13+2310c13+13]
< 172 = 289
|
Comp[]
|
13,?
|
|
03
|
13 < [30030n13+2310c13+17]
< 172 = 289
|
Comp[]
|
17,?
|
|
04
|
13 < [30030n13+2310c13+19]
< 172 = 289
|
Comp[]
|
19,?
|
|
05
|
13 < [30030n13+2310c13+23]
< 172 = 289
|
Comp[]
|
23,?
|
|
06
|
13 < [30030n13+2310c13+29]
< 172 = 289
|
Comp[]
|
29,?
|
|
07
|
13 < [30030n13+2310c13+31]
< 172 = 289
|
Comp[]
|
31,?
|
|
|
...
|
|
|
|
?
|
13 < [30030n13+2310c13+113]
< 172 = 289
|
Comp[]
|
113,?
|
|
?
|
13 < [30030n13+2310c13+127]
< 172 = 289
|
Comp[]
|
127,?
|
|
|
...
|
|
|
|
?
|
13 < [30030n13+2310c13+139]
< 172 = 289
|
Comp[]
|
139,?
|
|
?
|
13 < [30030n13+2310c13+149]
< 172 = 289
|
Comp[]
|
149,?
|
|
|
...
|
|
|
|
?
|
13 < [30030n13+2310c13+181]
< 172 = 289
|
Comp[]
|
181,?
|
|
?
|
13 < [30030n13+2310c13+191]
< 172 = 289
|
Comp[]
|
191,?
|
|
?
|
13 < [30030n13+2310c13+193]
< 172 = 289
|
Comp[]
|
193,?
|
|
?
|
13 < [30030n13+2310c13+197]
< 172 = 289
|
Comp[]
|
197,?
|
|
?
|
13 < [30030n13+2310c13+199]
< 172 = 289
|
Comp[]
|
199,?
|
|
?
|
13 < [30030n13+2310c13+211]
< 172 = 289
|
Comp[]
|
211,?
|
|
?
|
13 < [30030n13+2310c13+221]
< 172 = 289
|
Comp[0]
|
x,?
|
|
?
|
13 < [30030n13+2310c13+223]
< 172 = 289
|
Comp[]
|
223,?
|
|
?
|
13 < [30030n13+2310c13+227]
< 172 = 289
|
Comp[]
|
227,?
|
|
?
|
13 < [30030n13+2310c13+229]
< 172 = 289
|
Comp[]
|
229,?
|
|
?
|
13 < [30030n13+2310c13+233]
< 172 = 289
|
Comp[]
|
233,?
|
|
?
|
13 < [30030n13+2310c13+239]
< 172 = 289
|
Comp[]
|
239,?
|
|
?
|
13 < [30030n13+2310c13+241]
< 172 = 289
|
Comp[]
|
241,?
|
|
?
|
13 < [30030n13+2310c13+247]
< 172 = 289
|
Comp[0]
|
x,?
|
|
?
|
13 < [30030n13+2310c13+251]
< 172 = 289
|
Comp[]
|
251,?
|
|
?
|
13 < [30030n13+2310c13+257]
< 172 = 289
|
Comp[]
|
257,?
|
|
?
|
13 < [30030n13+2310c13+263]
< 172 = 289
|
Comp[]
|
263,?
|
|
?
|
13 < [30030n13+2310c13+269]
< 172 = 289
|
Comp[]
|
269,?
|
|
?
|
13 < [30030n13+2310c13+271]
< 172 = 289
|
Comp[]
|
271,?
|
|
?
|
13 < [30030n13+2310c13+277]
< 172 = 289
|
Comp[]
|
277,?
|
|
?
|
13 < [30030n13+2310c13+281]
< 172 = 289
|
Comp[]
|
281,?
|
|
?
|
13 < [30030n13+2310c13+283]
< 172 = 289
|
Comp[]
|
283,?
|
|
?
|
13 < [30030n13+2310c13+289]
< 172 = 289
|
Comp[]
|
289,?
|
|
?
|
13 < [30030n13+2310c13+293]
< 172 = 289
|
Comp[]
|
293,?
|
|
?
|
13 < [30030n13+2310c13+299]
< 172 = 289
|
Comp[0]
|
x,?
|
|
?
|
13 < [30030n13+2310c13+307]
< 172 = 289
|
Comp[]
|
307,?
|
|
?
|
13 < [30030n13+2310c13+311]
< 172 = 289
|
Comp[]
|
311,?
|
|
?
|
13 < [30030n13+2310c13+313]
< 172 = 289
|
Comp[]
|
313,?
|
|
?
|
13 < [30030n13+2310c13+317]
< 172 = 289
|
Comp[]
|
317,?
|
|
?
|
13 < [30030n13+2310c13+323]
< 172 = 289
|
Comp[]
|
323,?
|
|
?
|
13 < [30030n13+2310c13+331]
< 172 = 289
|
Comp[]
|
331?
|
|
?
|
13 < [30030n13+2310c13+337]
< 172 = 289
|
Comp[]
|
337?
|
|
|
...
|
|
|
|
480
|
13 < [30030n13+2310c13+2309]
< 172 = 289
|
Comp[]
|
2309?
|
As you can see, this gets rather ridiculous...
Effectively, at this point, it is just checking to see if the additive factor is divisible
by the prime, and then maintaining the record for later sieves.
Sieve-N:
Finds primes>N
The repeat distance is Prime[1]*Prime[2]*Prime[3]*...*N=2*3*5*7*11*...*N=Primorial[N]
Possible forms is LastForms*(N-1)
Includes: All primes>N and composites with prime factors>N
Excludes: All multiples of N not already excluded, (LastForms) branches
1st failure at (NextPrime[N])2
2nd failure at (NextPrime[N]*NextPrime[NextPrime[N]])
Assured prime range: N < primes < (NextPrime[N]*NextPrime[NextPrime[N]])
Mathematical Form is [RepeatDistance*nN+LastRepeat*cN+k]
where possible cN values are from 0..(N-1) and k retains info
from last sieve.
About the branching procedure:
Effectively, we are examining all the whole numbers n. We are then dividing the
numbers into various branches, in such a way that no number is ever lost or
double-counted. The sum of all the branches remains the sum of all the whole numbers.
Ex.
00 01 02 03 04 05 06
07 08 09 10 11 12 = [3n+0]
00 01 02 03 04 05 06 07
08 09 10 11 12 = [3n+1]
00 01 02 03 04 05 06 07 08
09 10 11 12 = [3n+2]
===================================
00 01 02 03 04 05 06 07 08 09 10 11 12 = [n]
Note that the additive factor ranges from (0..multiplicative factor-1). This is just
standard modulus algebra.
We are then excluding various branches from further examination, i.e. those that contain
only composites of the initial value.
Infinite count of prime numbers:
Based on this procedure, there can never be a greatest prime number.
Reasoning is as follows:
At each step, the next lowest prime number N found by a given sieve is used for the next
sieve.
The formula representation always assumes a solution form of N*n+c, with the condition that (N*n+c)
mod N<>0, which simplifies to (c) mod N<>0.
There are always (N-1) c-values for which this is true, based on simple modulus algebra.
This effectively creates (N-1) new branches for each new prime found, with 1 new branch
excluded, i.e. the composites of N.
If there was a greatest prime, it would have to "shut down" all current
branches, as all remaining numbers would have to be composites.
There is not a case where a given finite number N can "shut down" all the
branches, there are always (N-1) new branches created.
==================================
In fact, we can do even better, I can prove that there are an infinite # of
primes on each (non-all-composite) branch:
Use the following definitions:
Set PN=The set of all primes from P0 to PN,
where Pi = the ith Prime, i.e. P0=1, P1=2,
P2=3, P3=5, P4=7, etc.
Thus, PN = {P0, P1,
P2, P3, P4,...,PN} =
{1,2,3,5,7,11,13,17,...,PN}
Set PA and Set PB are formal, non-empty subsets of PN, such
that PA = ( PN and not PB ), PB = ( PN and
not PA )
Thus, ( PA union PB ) = PN, ( PA intersection PB
) = 0, where 0 is the Empty set.
Define SetProd[Set] as the product of all of the elements in the set.
Define (phi) = SetProd[PA] + SetProd[PB]
An example might take:
PN = P7 = {1,2,3,5,7}, PA = {1,3,5}, PB = {2,7}
SetProd[PA] = 1*3*5 = 15, SetProd[PB] = 2*7 = 14
(phi) = 15+14 = 29
Why is this interesting?
Because (phi) mod Pi <> 0 for i = (1..N)
(phi) mod Pi = ( SetProd[PA] + SetProd[PB] ) mod Pi
= ( SetProd[PA] mod Pi ), if Pi is in PB
or
= ( SetProd[PB] mod Pi ), if Pi is in PA
Thus, (phi) mod Pi <> 0 for i = (1..N) because Pi is not a
factor of the remaining product due to the way the sets were defined
Therefore, (phi) has one or more prime factors, each of which must be > PN
Therefore, given an arbitrary PN, we can construct the number (phi) has must contain a bigger
prime factor PM > PN
Iterating this process by letting PN --> PM each time proves that there are an Infnite # of
primes by construction.
We can make it even more general, by defining:
(phi) = SetProd[{Pimi}]+SetProd[{Pjnj}],
where (i) and (j)={0..N}; i and j don't overlap; m, n are positive integers.
In other words, we can make products of powers of primes, and the (phi) still
has the same property of being composed of primes PM > PN
====================================
Now, we can put (phi) in a convenient form by considering when one of the sets
contains a single element, and the other set contains all the rest.
N
(phi)=( Prod[Pi]/Pj )+( Pj )
i=0
Note that when we take Pj=1, we get
(phi) = Prod[Pi]/Pj + Pj
= Prod[Pi]/1 + 1 = Prod[Pi] + 1, which is the form used in the
standard textbook infinite # primes proof.
==============================
Now, using this, we show that there are an infinite number of primes in each of the
(non-all-composite) sieve
branches.
In Sieve-2, we have the form [6n+1] and [6n+5], and we excluded form [6n+3]
For form [6n+1] we compute (phi) = Prod[Pi]/Pj + Pj
= Prod[Pi]/1 + 1 = Prod[Pi] + 1
(Prod[Pi] + 1) mod Pk <> 0 for all k, where
k=(1..N)
Note that (Prod[Pi] + 1) = (2*3*RestProd[Pi] + 1) =
(6*RestProd[Pi] + 1) = (6n + 1)
For form [6n+5] we compute (phi) = Prod[Pi]/5 + 5
(Prod[Pi]/5 + 5) mod Pk <> 0 for all k, where
k=(1..N)
Note that (Prod[Pi]/5 + 5) = (2*3*RestProd[Pi]/5 + 5) =
(6*RestProd[Pi]/5 + 5) = (6n + 5)
What about the excluded form [6n+3]
For form [6n+3] we compute (phi) = Prod[Pi]/3 + 3
(Prod[Pi]/3 + 3) mod Pk <> 0 for all k, where
k=(1..N)
But, note that (Prod[Pi]/3 + 3) = (2*3*5*7*RestProd[Pi]/3 +
3) = (2*5*7*RestProd[Pi] + 3) <> (6n + 3)
(phi) cannot be put into the form [6n+3]
Because (6n+3)=3(2n+1), they are multiples of 3, hence, there cannot be an
infinite # of primes in form [6n+3]
For similar reasons, forms [6n+0], [6n+2], and [6n+4] would be excluded as well,
but they were already excluded in [2n+0]
=================
For form [30n+7] we compute (phi) = Prod[Pi]/7 + 7
(Prod[Pi]/7 + 7) mod Pk <> 0 for all k, where
k=(1..N)
Note that (Prod[Pi]/7 + 7) = (2*3*5*RestProd[Pi]/7 + 7) =
(30*RestProd[Pi]/7 + 7) = (30n + 7)
For form [30n+11] we compute (phi) = Prod[Pi]/11 + 11
(Prod[Pi]/11 + 11) mod Pk <> 0 for all k, where
k=(1..N)
Note that (Prod[Pi]/11 + 11) = (2*3*5*RestProd[Pi]/11 +
11) = (30*RestProd[Pi]/11 + 11) = (30n + 11)
...and so on...
We can always construct a (phi) which will be on a given branch.
Each of the sieve branches can be placed into this kind of form by construction.
Thus, on any given (non-all-composite) branch, there are an infinite # of prime numbers.
Therefore, as long as we exclude only branches containing multiples, the
remaining branches will each have an infinite # of primes on it.
Interesting tidbits:
Sieve-2 excludes 1/2 of all whole numbers
Sieve-3 excludes 1/6 of all whole numbers
Sieve-5 excludes 2/30 of all whole numbers
Sieve-7 excludes 8/210 of all whole numbers
Sieve-11 excludes 48/3210 of all whole numbers
Sieve-13 excludes 480/30030 of all whole numbers
(1/2)+(1/6)+(2/30)+(8/210)+(48/3210)+(480/30030)
(0.5)+(0.166666)+(0.066666)+(0.03809523809)+(0.01495327102)+(0.01598401598)=0.80236585841
>80% of all whole numbers are not prime
Click here to see extension to *Twin Primes*
Conjecture/Proof...
Now, we will examine the related procedure for twin primes:
* email John *
Back to the Science Realm: John's Virtual Sci+Tech Universe