Prime Number Sieve/Sieve of Eratosthenes

A mathematical model using formula analysis of prime numbers...

SiteMap of SciRealm | About John | 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) | Frontiers | IFS Fractals | JavaScript Graphics | JavaScript Graphics Using Table | Kid Science | Kryptos | Photography | Prime Sieve | QM from SR | QM from SR-Simple RoadMap | Quantum Phase | Quotes | RuneQuest Cipher Challenge | Secret Codes & Ciphers | Scientific Calculator | Science+Math | Sci-Pan Pantheist Poems | Stereograms | Turkish Grammar

Welcome to 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 QM from SR-Simple RoadMap

***Learn, Discover, Explore***

Melike Wilson Art

Site last modified: 2015-Apr-25



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


 
0001, [0203040506,  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

  000102, [03040506070809,
 
10111213141516,  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

  0001020304, [0506070809,
 
10111213141516171819,
 
20212223242526272829,
 
30313233343536,  37,  3839,
 
40,  41,  42,  43,  444546,  47,  48,  49,
 
505152,  53,  54,  55,  565758,  59,
 
60,  61,  626364,  65,  66,  67,  6869,
 
70,  71,  72,  73,  747576,  77,  78,  79,
 
808182,  83,  84,  85,  868788,  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

  00010203040506, [070809,
  10
111213141516171819,
  202122
23242526272829,
  30
313233343536373839,
  40
414243444546474849,
  505152
53545556575859,
  60
616263646566676869,
  70
7172737475767778,  79,
  808182,  83,  84
85868788,  89,
  90,  91,  929394
9596,  97,  9899,
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?/

  00010203040506070809,
  10, [
111213141516171819,
  202122
23242526272829,
  30
313233343536373839,
  40
414243444546474849,
  505152
53545556575859,
  60
616263646566676869,
  70
717273747576777879,
  808182
83848586878889,
  90
919293949596979899,
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?,...

  00010203040506070809,
  10
1112, [13141516171819,
  202122
23242526272829,
  30
313233343536373839,
  40
414243444546474849,
  505152
53545556575859,
  60
616263646566676869,
  70
717273747576777879,
  808182
83848586878889,
  90
919293949596979899,
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
The Science Realm: John's Virtual Sci-Tech Universe
John's Science & Math Stuff: | About John | Send email to John
4-Vectors | Ambigrams | Antipodes | Covert Ops Fragments | Cyrillic Projector | Forced Induction (Sums Of Powers Of Integers) | Fractals | Frontiers |
JavaScript Graphics | Kid Science | Kryptos | Photography | Prime Sieve | QM from SR | QM from SR-Simple RoadMap | Quantum Phase | Quotes |
RuneQuest Cipher Challenge | Scientific Calculator | Secret Codes & Ciphers | Science+Math | Sci-Pan Pantheist Poems | Stereograms | Turkish Grammar |

Quantum Mechanics is derivable from Special Relativity
See QM from SR-Simple RoadMap