# Primorials and the Next Prime

by Playdo
Tags: prime, primorials
 P: 92 Theorem 1: Given a primorial $p_n^{\sharp}>2$, $p_{n+1}$ is the second largest element in the reduced residue system modulo $p_n^{\sharp}$. Proof Clearly $p_{n+1}$ is an element of the r.r.s. modulo $p_n^{\sharp}$ since every prime less than $p_{n+1}$ divides $p_n^{\sharp}$. Next notice that the smallest element of the r.r.s. modulo $p_n^{\sharp}$ is invariably one. So it remains to show that the second largest element in r.r.s. modulo $p_n^{\sharp}$ is in fact prime. But wait this is already done since every prime less than this second element is a factor of $p_n^{\sharp}$ and the two are relatively prime, the second element must be prime and it must be the next prime. q.e.d. Lemma 1: It follows immediately that the third element in the r.r.s. modulo $p_n^{\sharp}$ is either prime or divisible by the second element in the r.r.s. modulo $p_n^{\sharp}$. Further extension along these lines is possible. Theorem 2: We can construct a sequence of prime numbers using the sequence of primorials $p^{\sharp}$ greater than two and the reduced residue systems of this sequence. Proof We are given $p_2^{\sharp}=6$ and r.r.s. modulo 6 = {1,5} By Theorem1 $5=p_3$. We can write the r.r.s. modulo $p_3^{\sharp}=30$ using the reduced residue system modulo 6 as follows [tex]r.r.s. mod 30 = \{6x+r_{i}|r_{i} \in r.r.s. mod 6, 0
HW Helper
P: 1,994
 Quote by Playdo Theorem 1: Given a primorial $p_n^{\sharp}>2$, $p_{n+1}$ is the second largest element in the reduced residue system modulo $p_n^{\sharp}$.
I guess you mean "second smallest"? i.e. the smallest n>1 relatively prime to p#.

 Quote by Playdo Eq. 1 [tex]r.r.s. modulo p_{n+1}^{\sharp} = \{p_n^{\sharp}x+r_{i}|r_{i} \in r.r.s. mod p_n^{\sharp}, 0
This doesn't work as you've written it. Even when n=2 this set you are trying to subtract off doesn't give what you want. To have 25 is this set you are removing, you'd need r_j*r_i=5, but this isn't =1 mod 2*3. You want to remove {p_{n+1}*r| r is in the rrs of p_{n}#}.

Have you looked up the "wheel sieve" yet (Hurkyl mentioned it to you before)? There's an article "Explaining the Wheel Sieve" by Pritchard, from the early '80s' that you should find.

 Quote by Playdo Define the following operations on sets.
I have no idea what you are trying to accomplish by introducing some strange notation that doesn't appear to simplify anything (and that kernel thing for the set you remove is still not what you want).
P: 92
 Quote by shmoe I guess you mean "second smallest"? i.e. the smallest n>1 relatively prime to p#. This doesn't work as you've written it. Even when n=2 this set you are trying to subtract off doesn't give what you want. To have 25 is this set you are removing, you'd need r_j*r_i=5, but this isn't =1 mod 2*3. You want to remove {p_{n+1}*r| r is in the rrs of p_{n}#}. Have you looked up the "wheel sieve" yet (Hurkyl mentioned it to you before)? There's an article "Explaining the Wheel Sieve" by Pritchard, from the early '80s' that you should find. I have no idea what you are trying to accomplish by introducing some strange notation that doesn't appear to simplify anything (and that kernel thing for the set you remove is still not what you want).
Nope, I will find that article. I had a professor in math grad school who also understood the wheel sieve, discovered it on his own but never wrote it down.

Yup I see that it does not work that second term. What we really want is to subtract this $p_{n+1}r.r.s._{[p_n^{\sharp}]}$.

On the notation I want to investigate equations where we have combinations of arithmetic bases and modular operations like 100111 base 2 congruent to 23456 base ten mod 7 mod 6. That is really not connected to this thread, so I should have just started a different one.

notice that in fact every element of the redeced residue system for the primorial is prime up to the square of the second element. With each larger primorial we get a larger and larger set of primes added by this principle. The problem is that the primorials grow much faster than the squares of consecutive primes, so the return compared to storage needed is eventually miniscule.

But what I am wondering is if there is way to develop and algorithm that generates primes form the reduced residue systems (as I have described) without needing to explicitly know the entire r.r.s.?

For instance, we know how to right the reduced residue system for the n+1 st prime in terms of the residue system of the nth prime. Infact we can do so in an ordered way. So it would remain only to identify p[n+1]^2 in that ordered set, that is solve the equation $p_{n+1}^2=p_n^{\sharp}x+r_i$ where r[i] is an element of the reduced residue system modulo p[n]. But we know that the next prime is the second element of the reduced residue system so we have that and the division algorithm gives us x and r, but we do not have i. We could get i by one run thorugh the ordered rduced residue modulo p[n]. Ok so here is my attempt at fleshing out an algorithm.

1) starting with base 30, form the ordered reduced residue system mod 30.
2) the second element is the next prime, by Theorem 1, that is seven, so square it to get forty-nine. Every element in r.r.s. mod thirty that is less than 49 is prime, which is everything.

"Up one rung"

1) write out the reduced residue system modulo 210 using Equation 1 (the corrected equation) in an ordered way as $30x+r[i], x \in \{0,..,p_{n+1} -1\}$
2) Seven has been removed it will go into the base as 30*7-210. So eleven is the smallest save 1. 11^2=121. 121 mod 30 is 1, div 30 is 4 so the new set of primes is $30x+r[i], x \in \{0,..,4}$ the index of 1 in the r.r.s. mod 30 is 1 so once we get to (x,r)=(4,1) we stop.

"Up one rung"

1) write out the reduced residue system modulo 2310 using Equation 1 ... (?)

2) 11 has now been removed and will go into the base 11*210=2310. So thirteen is the smallest save 1. 13^2=169, 169 is within the reduced residue system mod 210 so simply accept as prime (they are prime) the elements between 121 and 169. 11*13 was already removed (?), it seems like the way it is set up now certain square free numbers are left in as we go higher.

Well it needs some work to be sure. The rate at which the primorials grow is quickly destroying the effectiveness of the sieve it appears. I'll have to go back and crank out the numerical examples step by step to see if I may not be seeing something. It does'nt feel quite right though.

I will find that article Hurkyl mentioned.

Later

 P: 92 Primorials and the Next Prime Eq. 1 [tex]r.r.s. modulo p_{n+1}^{\sharp} = \{p_n^{\sharp}x+r_{i}|r_{i} \in r.r.s. mod p_n^{\sharp}, 0
 Sci Advisor HW Helper P: 1,994 If you wanted primes up to N, you don't need to find the rrs of p# where p is the largest prime less than sqrt(N). You would only need the bits that are less than N. For example, using the wheel sieve up to 27 say. You'd find the rrs mod 6, {1,5}, then roll it along, stopping at 27 to get the set {1,5,7,11,13,17,19,23,25}. Then remove the multiples of 5 and you'd be done since 7^2>27. You never need to look higher than 27. This is more pronounced when sieving up to higher values, you'll have lots of steps where you don't really 'roll the wheel' at all, i.e. you can entirely skip adding stuff to get the rrs of p_{n+1}# from the rrs of p_{n} since the new elements lie above N, you just remove the multiples of p_{n+1}. The fast growth of p# doesn't cause memory problems.
P: 92
 Quote by shmoe If you wanted primes up to N, you don't need to find the rrs of p# where p is the largest prime less than sqrt(N). You would only need the bits that are less than N. For example, using the wheel sieve up to 27 say. You'd find the rrs mod 6, {1,5}, then roll it along, stopping at 27 to get the set {1,5,7,11,13,17,19,23,25}. Then remove the multiples of 5 and you'd be done since 7^2>27. You never need to look higher than 27. This is more pronounced when sieving up to higher values, you'll have lots of steps where you don't really 'roll the wheel' at all, i.e. you can entirely skip adding stuff to get the rrs of p_{n+1}# from the rrs of p_{n} since the new elements lie above N, you just remove the multiples of p_{n+1}. The fast growth of p# doesn't cause memory problems.
Ok then that is exactly what I meant. It is beautiful if we are allowed such notions these days. I did not realize that was already well known, and I certainly did not mean it as an insult.

A question I still have is why do we keep on thinking there must be faster factorization algorithms? Just in pure computing aspects alone there will always be a next number that cannot be factored easily. Natural numbers with only too large prime factors become relatively less dense as we head off to infinity, still it ultimately comes down to parallel processing and speed doesn't it?

What would be your take on that? Are there still faster algorithms to be found or is that mostly exhausted? Are we not now just talking about ever increasing speed and parallel processing to try to factor larger numbers?

What if Goldbach lies outside those truths we can prove? What if it is a Godel Incompleteness issue? Could we always tell?

It seems like we have some agreement then on that notion of the wheel sieve. I'm tired, see you later.
HW Helper
P: 1,994
 Quote by Playdo It is beautiful if we are allowed such notions these days.
when weren't we?

 Quote by Playdo A question I still have is why do we keep on thinking there must be faster factorization algorithms? Just in pure computing aspects alone there will always be a next number that cannot be factored easily. Natural numbers with only too large prime factors become relatively less dense as we head off to infinity, still it ultimately comes down to parallel processing and speed doesn't it? What would be your take on that? Are there still faster algorithms to be found or is that mostly exhausted? Are we not now just talking about ever increasing speed and parallel processing to try to factor larger numbers?
I would very much doubt that we have reached the pinnacle of factoring algorithms. Improvements and new algorithms entirely keep appearing, I don't see anything that suggests this will stop.

 Quote by Playdo What if Goldbach lies outside those truths we can prove? What if it is a Godel Incompleteness issue? Could we always tell?
Honestly, does it matter? There are plenty of conjectures in number theory (and all of math in general) that won't be resolved in my lifetime, and perhaps never at all. This doesn't mean all the work towards their resolution is a waste of time (even if they are impossible to prove and we don't know this), partial results can still be very interesting and/or useful.
 P: 92 Very true and well said. You seem so much more positive, it's very refreshing. Has your paper on category theory been published, or was that Hurk?
 P: 3 Yes Playdo, you are in right direction. But you already know about my preprint in the eljose's posting: http://www.ma.utexas.edu/mp_arc/c/06/06-314.pdf What you are saying about the rss is exactly the sequences of numbers which I call "generations". But you failed to notice the more important things about the generations, they have notably symmetries. And studying the recursive sieve I define in my paper it is trivial to demonstrate the prime number theorem.
 P: 3 Sorry I meant rrs in the previous post.

 Related Discussions General Math 10 Linear & Abstract Algebra 6 Linear & Abstract Algebra 0 Linear & Abstract Algebra 5 Linear & Abstract Algebra 14