Goahead52's posts about primes

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Goahead52's posts about primes

Postby Goahead52 » Mon Feb 29, 2016 2:00 pm UTC

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=19-b1=1
c2=23-b2=21
c3=29-b3=6
c4=31-b4=29
c5=37-b5=16
c6=41-b6=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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Mon Feb 29, 2016 7:31 pm UTC

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.

User avatar
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

Postby Xanthir » Mon Feb 29, 2016 7:45 pm UTC

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)))

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Mon Feb 29, 2016 8:03 pm UTC

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.

PsiSquared
Posts: 126
Joined: Wed May 09, 2012 6:02 pm UTC

Re: Algorithm : Finding the biggest prime ever

Postby PsiSquared » Mon Feb 29, 2016 8:26 pm UTC

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?

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Wed Mar 02, 2016 12:41 pm UTC

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?

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby PsiCubed » Fri Mar 04, 2016 10:17 am UTC

Well, the advantage of starting with a primorial quickly becomes negligible as the numbers get larger.

For example, 149# is 58-digit number. Its square root has 29-digits, 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 58-digit 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 58-digit 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#).
Image

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Fri Mar 04, 2016 7:37 pm UTC

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.
Last edited by Goahead52 on Fri Mar 04, 2016 7:55 pm UTC, edited 1 time in total.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Fri Mar 04, 2016 7:53 pm UTC

I can use semi-prime 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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby Goahead52 » Sat Mar 05, 2016 5:32 pm UTC

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 semi-primes 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.

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Subsets and product of primes

Postby Goahead52 » Wed Mar 09, 2016 6:13 pm UTC

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

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: Algorithm : Finding the biggest prime ever

Postby PsiCubed » Thu Mar 10, 2016 6:32 am UTC

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 non-trivial 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 prime-testing 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.
Image

curiosityspoon
Posts: 36
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Subsets and product of primes

Postby curiosityspoon » Thu Mar 10, 2016 6:37 am UTC

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 .

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: Subsets and product of primes

Postby PsiCubed » Thu Mar 10, 2016 6:41 am UTC

And just in case anybody hopes that all the numbers in this sequence are prime:

5448239 = 67x233x349

So no such luck.
Image

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Re: Subsets and product of primes

Postby Goahead52 » Fri Mar 11, 2016 7:32 pm UTC

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....

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: Subsets and product of primes

Postby PsiCubed » Sun Mar 13, 2016 4:19 am UTC

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,000-digit numbers for primality in any reasonable time. The only reason this record is so high, is that it is a number of the form 2n-1, for which there is a special test which is very efficient (the Lucas-Lehmer 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 2n-1, and find a way to improve the current results by a few orders of magnitude.
2. Devise, from scratch, a test similar to Lucas-Lehmer 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 100-million digit prime.
Image

Goahead52
Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

Limit

Postby Goahead52 » Mon Mar 14, 2016 7:21 pm UTC

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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26829
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Goahead52's posts about primes

Postby gmalivuk » Mon Mar 14, 2016 9:03 pm UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests