Goahead52's posts about primes
Moderators: gmalivuk, Moderators General, Prelates
Goahead52's posts about primes
Hi everyone,
Here is my discovery.
How to build the biggest prime ever?
My algorithm illustrated by an example.
Start with some primorial #17=2*3*5*7*11*13*17=510510
Compute a=int(sqrt(510510))=714
List the first few primes > 17
19,23,29,31,37,41....
You do not need to list them all up to the last prime < 714.
Compute :
b1=#17 = 18 mod 19
b2=#17 = 2 mod 23
b3=#17 = 23 mod 29
b4=#17 = 2 mod 31
b5=#17 = 21 mod 37
b6=#17 = 19 mod 41
....
Compute :
c1=19b1=1
c2=23b2=21
c3=29b3=6
c4=31b4=29
c5=37b5=16
c6=41b6=22
.....
You do the computation until you a pair of primes (31,29).
c4=29 is prime and 31 which is the fourth listed prime 31 is prime too.
Once you reach the first condition above you have to check if both are > 17 (17 is the last prime of the primorial of #17).
The second condition if fullfilled :
29>17
31>17
Compute the product of the pair 29*31=899
Add 899 to #17 = 510510+899=511409
Now compute : int(sqrt(511409))=715
715 is not prime and the last prime is < a (see above)
Hence the third condition is fulfilled.
Once the three conditions are fulfilled we can be sure that 511409 is a certified prime.
I tried with many other values. I hope I did not miscalculate. It always works.
I do not know how to prove my results.
What I want to do is first to check my algorithm to see if there are counterexamples.
If my result is sure then how to prove it.
Thank you.
In any case even if the discovery is confirmed it will have a huge impact on the number theory.
Assuming that there is some mistake somewhere can we improve it to make it better?
Thank you for your time and your help.
Here is my discovery.
How to build the biggest prime ever?
My algorithm illustrated by an example.
Start with some primorial #17=2*3*5*7*11*13*17=510510
Compute a=int(sqrt(510510))=714
List the first few primes > 17
19,23,29,31,37,41....
You do not need to list them all up to the last prime < 714.
Compute :
b1=#17 = 18 mod 19
b2=#17 = 2 mod 23
b3=#17 = 23 mod 29
b4=#17 = 2 mod 31
b5=#17 = 21 mod 37
b6=#17 = 19 mod 41
....
Compute :
c1=19b1=1
c2=23b2=21
c3=29b3=6
c4=31b4=29
c5=37b5=16
c6=41b6=22
.....
You do the computation until you a pair of primes (31,29).
c4=29 is prime and 31 which is the fourth listed prime 31 is prime too.
Once you reach the first condition above you have to check if both are > 17 (17 is the last prime of the primorial of #17).
The second condition if fullfilled :
29>17
31>17
Compute the product of the pair 29*31=899
Add 899 to #17 = 510510+899=511409
Now compute : int(sqrt(511409))=715
715 is not prime and the last prime is < a (see above)
Hence the third condition is fulfilled.
Once the three conditions are fulfilled we can be sure that 511409 is a certified prime.
I tried with many other values. I hope I did not miscalculate. It always works.
I do not know how to prove my results.
What I want to do is first to check my algorithm to see if there are counterexamples.
If my result is sure then how to prove it.
Thank you.
In any case even if the discovery is confirmed it will have a huge impact on the number theory.
Assuming that there is some mistake somewhere can we improve it to make it better?
Thank you for your time and your help.
Re: Algorithm : Finding the biggest prime ever
Someone has found a counter example with #19 and the pair 47,29
I need to rethink the conditions.
Any idea to improve the algo is welcomed.
I need to rethink the conditions.
Any idea to improve the algo is welcomed.
 Xanthir
 My HERO!!!
 Posts: 5426
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Algorithm : Finding the biggest prime ever
As far as I know, no algorithm that doesn't involve just directly testing for primality will ever generate primes with 100% certainty  their structure is "too random". Some algos are *good* at generating primes, or can generate numbers with special forms that are easy to test for primality, but nothing is 100%.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Algorithm : Finding the biggest prime ever
Xanthir wrote:As far as I know, no algorithm that doesn't involve just directly testing for primality will ever generate primes with 100% certainty  their structure is "too random". Some algos are *good* at generating primes, or can generate numbers with special forms that are easy to test for primality, but nothing is 100%.
I agree with you.
But I`m always trying to find a way to skip testing all the primes < int(sqrt(N)).
I need to fix my conditions. I`m not giving up for now.

 Posts: 126
 Joined: Wed May 09, 2012 6:02 pm UTC
Re: Algorithm : Finding the biggest prime ever
Goahead52 wrote:Xanthir wrote:As far as I know, no algorithm that doesn't involve just directly testing for primality will ever generate primes with 100% certainty  their structure is "too random". Some algos are *good* at generating primes, or can generate numbers with special forms that are easy to test for primality, but nothing is 100%.
I agree with you.
But I`m always trying to find a way to skip testing all the primes < int(sqrt(N)).
I need to fix my conditions. I`m not giving up for now.
Oh, there are many ways to skip "testing all the primes <int(sqrt(N))". And there's at least one method which is simple enough for you to discover on your own (and which can be implemented on any standard scientific calculator).
But you're unlikely to find anything by trying stuff blindly (which is what you seem to be doing). The odds of such an approach succeeding are virtually nil. And even if you did manage to find a correct algorithm in this manner, how would you know that it always works?
Re: Algorithm : Finding the biggest prime ever
Here is my new draft.
I`m sorry my previous mistakes. I`m too lazy to write a complete paper to show how to build a biggest prime.
My method starting from an example Primorial 7
I compute :
#7=2*3*5*7=210
What is the number A to be added to #7 such as #7+A will be prime for sure?
Condition 1 :
The integer number A must be :
 either prime > 7
 or odd composite number with the lowest factor > 7
Here is the list of the potential candidates :
11,13
Condition 2 :
The number A must not exceed the last prime < int(sqrt(#p+A))
I compute the int(sqrt(#7))=14
The last prime number < 14 is 13
Condition 3 :
Sieving the set of the potential candidates
I start by computing #7 mod 11
#7= 1 mod 11
Then
#7=2 mod 13
If we add 11 to #7 = 221 will not be divided by 11.
So we need to check if 221 is divisible by the remaining number on the list 13.
221 is divisible by 13.
Hence 11 is removed from the list.
The only number remaining is 13.
210+13=223 is then for sure a prime number.
Our list here is very short.
But as #p grow the list grow quickly.
For #11=2*3*5*7*11=2310 the list of the potential candidates will be : 13,17,19,23,29,31,37,41,47 because int(sqrt(2310))=48
At this stage I still think that we do not need to check all the numbers of this list.
I`m blocked as long as I did not find a way to check only few numbers to claim that the number created is for sure prime.
Any idea?
I`m sorry my previous mistakes. I`m too lazy to write a complete paper to show how to build a biggest prime.
My method starting from an example Primorial 7
I compute :
#7=2*3*5*7=210
What is the number A to be added to #7 such as #7+A will be prime for sure?
Condition 1 :
The integer number A must be :
 either prime > 7
 or odd composite number with the lowest factor > 7
Here is the list of the potential candidates :
11,13
Condition 2 :
The number A must not exceed the last prime < int(sqrt(#p+A))
I compute the int(sqrt(#7))=14
The last prime number < 14 is 13
Condition 3 :
Sieving the set of the potential candidates
I start by computing #7 mod 11
#7= 1 mod 11
Then
#7=2 mod 13
If we add 11 to #7 = 221 will not be divided by 11.
So we need to check if 221 is divisible by the remaining number on the list 13.
221 is divisible by 13.
Hence 11 is removed from the list.
The only number remaining is 13.
210+13=223 is then for sure a prime number.
Our list here is very short.
But as #p grow the list grow quickly.
For #11=2*3*5*7*11=2310 the list of the potential candidates will be : 13,17,19,23,29,31,37,41,47 because int(sqrt(2310))=48
At this stage I still think that we do not need to check all the numbers of this list.
I`m blocked as long as I did not find a way to check only few numbers to claim that the number created is for sure prime.
Any idea?
Re: Algorithm : Finding the biggest prime ever
Well, the advantage of starting with a primorial quickly becomes negligible as the numbers get larger.
For example, 149# is 58digit number. Its square root has 29digits, so the fact that you've already eliminated all possible divisors below 149 doesn't really matter.
On the other hand, you can use statistics to speed up your search. If you check  say  a random 1000 58digit numbers for primility, you're virtually guaranteed to find a prime. So unless you can reduce the number of candidates of the form 149#+N to less than a thousand, you'll be better off simply trying random numbers of the desired size.
Either way, you'll need an efficient test to check each candidate (except, possibly, the last one which you know is prime because it is the last one left). And since naïve trial division of a 58digit number would take millions of years, you should focus your efforts on finding better ways to test individual numbers rather than limiting the number of possible candidates to check.
EDITED TO ADD: I don't think you can assume that there's always a prime between p# and p#+sqrt(p#).
For example, 149# is 58digit number. Its square root has 29digits, so the fact that you've already eliminated all possible divisors below 149 doesn't really matter.
On the other hand, you can use statistics to speed up your search. If you check  say  a random 1000 58digit numbers for primility, you're virtually guaranteed to find a prime. So unless you can reduce the number of candidates of the form 149#+N to less than a thousand, you'll be better off simply trying random numbers of the desired size.
Either way, you'll need an efficient test to check each candidate (except, possibly, the last one which you know is prime because it is the last one left). And since naïve trial division of a 58digit number would take millions of years, you should focus your efforts on finding better ways to test individual numbers rather than limiting the number of possible candidates to check.
EDITED TO ADD: I don't think you can assume that there's always a prime between p# and p#+sqrt(p#).
Re: Algorithm : Finding the biggest prime ever
Thank you.
What I have found to be sure that #p+A is for sure prime is that you need to compute #p mod q where q represents all the primes between p and the last prime before int(sqrt(#p)).
Example for #19 you need to compute 425 primes which is undoable when p goes very large.
Out of 425 primes I selected 158 giving almost all the primes > 23 and <=3109
I have to find another way.
What I have found to be sure that #p+A is for sure prime is that you need to compute #p mod q where q represents all the primes between p and the last prime before int(sqrt(#p)).
Example for #19 you need to compute 425 primes which is undoable when p goes very large.
Out of 425 primes I selected 158 giving almost all the primes > 23 and <=3109
I have to find another way.
Last edited by Goahead52 on Fri Mar 04, 2016 7:55 pm UTC, edited 1 time in total.
Re: Algorithm : Finding the biggest prime ever
I can use semiprime numbers. So the list will be short.
I will have then to solve a diophantine equation as the large prime < r is 3109
mn<3019 (where m and n are primes > p
It needs lot of work.
No one could guaranty me that such number added to #p will be prime.
Anyway thank you very much.
I will have then to solve a diophantine equation as the large prime < r is 3109
mn<3019 (where m and n are primes > p
It needs lot of work.
No one could guaranty me that such number added to #p will be prime.
Anyway thank you very much.
Re: Algorithm : Finding the biggest prime ever
The step of sieving potential candidate could be very quick.
Example :
#19=15 mod 23 hence some primes will be removed like 31,307,353,etc... because if we add 31+#19 the result will be divisible by 23. The same holds for 307,353....
So we could apply the algo to the first prime remaining on our list until the last one 3109.
This step in particular could be optimized.
Another idea is : as #p grows we could limit our search to the product of 3,4,...k primes.
For #19 there are few semiprimes m*n (m and n odd primes<p) such as m*n < 3109
I do not know for sure that at least one of the product added to #p will give a prime. It is an open number theory problem.
Example :
#19=15 mod 23 hence some primes will be removed like 31,307,353,etc... because if we add 31+#19 the result will be divisible by 23. The same holds for 307,353....
So we could apply the algo to the first prime remaining on our list until the last one 3109.
This step in particular could be optimized.
Another idea is : as #p grows we could limit our search to the product of 3,4,...k primes.
For #19 there are few semiprimes m*n (m and n odd primes<p) such as m*n < 3109
I do not know for sure that at least one of the product added to #p will give a prime. It is an open number theory problem.
Subsets and product of primes
Hi,
Let P be the set of consecutive prime numbers from 2 to p {2,3,5,7,11,.....,p}
We split the set in 2 subsets P1 and P2 such as P1 U P2 = P and intersection of P1 and P2 = Empty set.
Example P = {2,3,5,7,11,13,17,19}
P1={2,5,7,11,13}
P2={3,17,19}
Or
P1={3,7,17,19}
P2={2,5,11,13}
Let us compute
A=product of all elements of the set P1
B=product of all elements of the set P2
Example
A=2*5*7*11*13=10010
B=3*17*19=969
We want the minimal value of M=A+B
P={2,3}
M=5
P={2,3,5}
M=11
P={2,3,5,7}
M=29
P={2,3,5,7,11}
M=97
P={2,3,5,7,11,13}
M=353
and so on
I have not found the sequence in OEIS
Is there any way to have an approximation of M in relation with Card(P)
2> 5
3> 11
4....? 29
5> 97
6> 353
Card(P)> M = f(Card*P)?
Thank you for any clue or idea
Let P be the set of consecutive prime numbers from 2 to p {2,3,5,7,11,.....,p}
We split the set in 2 subsets P1 and P2 such as P1 U P2 = P and intersection of P1 and P2 = Empty set.
Example P = {2,3,5,7,11,13,17,19}
P1={2,5,7,11,13}
P2={3,17,19}
Or
P1={3,7,17,19}
P2={2,5,11,13}
Let us compute
A=product of all elements of the set P1
B=product of all elements of the set P2
Example
A=2*5*7*11*13=10010
B=3*17*19=969
We want the minimal value of M=A+B
P={2,3}
M=5
P={2,3,5}
M=11
P={2,3,5,7}
M=29
P={2,3,5,7,11}
M=97
P={2,3,5,7,11,13}
M=353
and so on
I have not found the sequence in OEIS
Is there any way to have an approximation of M in relation with Card(P)
2> 5
3> 11
4....? 29
5> 97
6> 353
Card(P)> M = f(Card*P)?
Thank you for any clue or idea
Re: Algorithm : Finding the biggest prime ever
I think that using your basic idea, the quickest way to find a prime is not to do any sieving at all. Just test a few random numbers of the form 19#+N, where N<sqrt(19#) being some number whose smallest prime factor is bigger than 19.
The odds of getting a hit is roughly 2log(19)/log(19#) or 37%. Repeat this 5 times, and your chances rise to 90%. And after 10 tries, you have a 99% chance of hitting a prime.
Let me give it a shot:
19#+127 = 9699817 which is prime.
Waddayaknow? I got lucky and found a prime on my first try.
Now you try it. You're 99% certain to get a prime by your 10th attempt. And I don't think any amount of sieving is going to reduce the number of candidates to less than 10. It seems that the "naïve" way of shooting in the dark and hoping for success may well be the fastest way to find your prime.
Also, remember that no matter how good your "candidate finding" algorithm is, there still remains the nontrivial problem of actually testing the numbers for primality. If the only test you know is "checking all possible factors up to sqrt(N)" then this will quickly become unfeasible.
And the reverse is also true: If you have a quick primetesting algorithm at your disposal, then finding better sieving techniques becomes less important. If you can test one candidate in a reasonable time, you can probably test a few dozens of them without too much effort.
The odds of getting a hit is roughly 2log(19)/log(19#) or 37%. Repeat this 5 times, and your chances rise to 90%. And after 10 tries, you have a 99% chance of hitting a prime.
Let me give it a shot:
19#+127 = 9699817 which is prime.
Waddayaknow? I got lucky and found a prime on my first try.
Now you try it. You're 99% certain to get a prime by your 10th attempt. And I don't think any amount of sieving is going to reduce the number of candidates to less than 10. It seems that the "naïve" way of shooting in the dark and hoping for success may well be the fastest way to find your prime.
Also, remember that no matter how good your "candidate finding" algorithm is, there still remains the nontrivial problem of actually testing the numbers for primality. If the only test you know is "checking all possible factors up to sqrt(N)" then this will quickly become unfeasible.
And the reverse is also true: If you have a quick primetesting algorithm at your disposal, then finding better sieving techniques becomes less important. If you can test one candidate in a reasonable time, you can probably test a few dozens of them without too much effort.

 Posts: 36
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Subsets and product of primes
First off, your term for 6 is wrong: the minimal partition there is actually 3,5,11 vs. 2,7,13 (165 x 182), for a sum of 347. With the correct value in its place, we find https://oeis.org/A182987 .
Re: Subsets and product of primes
And just in case anybody hopes that all the numbers in this sequence are prime:
5448239 = 67x233x349
So no such luck.
5448239 = 67x233x349
So no such luck.
Re: Subsets and product of primes
If we pick randomly the set P1 (P2 will be the complement to P of P1) we will obtain C=A+B.
C has some probability to be prime. For sure the probability will decrease as Card(P) grow.
For larger sets we could use simulation to estimate the probability of obtaining C prime.
What if instead of picking randomly the P1 we build a strategy to choose P1 such as C=A+B will be for sure prime?
There are lot conditions to define to reach such result.
I have no idea for now about the conditions to determine such as C will be prime.
By using modular equations (CRT or something else) we could have some results.
Another way is to split P in 2^k sets where k>1
The last method require some conditions for partitioning the set P
Still thinking....
C has some probability to be prime. For sure the probability will decrease as Card(P) grow.
For larger sets we could use simulation to estimate the probability of obtaining C prime.
What if instead of picking randomly the P1 we build a strategy to choose P1 such as C=A+B will be for sure prime?
There are lot conditions to define to reach such result.
I have no idea for now about the conditions to determine such as C will be prime.
By using modular equations (CRT or something else) we could have some results.
Another way is to split P in 2^k sets where k>1
The last method require some conditions for partitioning the set P
Still thinking....
Re: Subsets and product of primes
Basically, you get the same result you did on the other thread.
C cannot divide any of the primes that exist in A and B... and that's it. The odds of C being prime are about the same as the odds of p#+N being prime on the other thread.
By the way, if your goal is to get the "largest prime ever", keep in mind that the current record prime has over 20,000,000 digits. And right now, nobody knows how to test general 20,000,000digit numbers for primality in any reasonable time. The only reason this record is so high, is that it is a number of the form 2^{n}1, for which there is a special test which is very efficient (the LucasLehmer test, which still takes months to complete with optimized software).
So if you want to break this record, you'll need to either:
1. Concentrate on numbers of the form 2^{n}1, and find a way to improve the current results by a few orders of magnitude.
2. Devise, from scratch, a test similar to LucasLehmer for primorials and then improve the results by a few orders of magnitude.
Options #1 seems easier. Although it is still very very difficult. The good new is, that if you succeed, you'll probably win $150,000. Because that's the prize for finding the first 100million digit prime.
C cannot divide any of the primes that exist in A and B... and that's it. The odds of C being prime are about the same as the odds of p#+N being prime on the other thread.
By the way, if your goal is to get the "largest prime ever", keep in mind that the current record prime has over 20,000,000 digits. And right now, nobody knows how to test general 20,000,000digit numbers for primality in any reasonable time. The only reason this record is so high, is that it is a number of the form 2^{n}1, for which there is a special test which is very efficient (the LucasLehmer test, which still takes months to complete with optimized software).
So if you want to break this record, you'll need to either:
1. Concentrate on numbers of the form 2^{n}1, and find a way to improve the current results by a few orders of magnitude.
2. Devise, from scratch, a test similar to LucasLehmer for primorials and then improve the results by a few orders of magnitude.
Options #1 seems easier. Although it is still very very difficult. The good new is, that if you succeed, you'll probably win $150,000. Because that's the prize for finding the first 100million digit prime.
Limit
Hi,
#p=2*3*5*7*11*13*.....*p
r=int(sqrt(#p))
d = the number of primes between p and r
s = the number of primes < r
What is the limit of d/s when p goes to infinity?
I conjecture that d/s will near 0 when p goes to infinity.
I can not prove it.
#p=2*3*5*7*11*13*.....*p
r=int(sqrt(#p))
d = the number of primes between p and r
s = the number of primes < r
What is the limit of d/s when p goes to infinity?
I conjecture that d/s will near 0 when p goes to infinity.
I can not prove it.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26836
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Goahead52's posts about primes
You don't need to start a new thread for every new thought you have about products of primes, so I've merged the three that already existed, and I'll merge any future ones into this.
Who is online
Users browsing this forum: No registered users and 9 guests