My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree2Thanks
  • 1 Post By danaj
  • 1 Post By danaj
Reply
 
LinkBack Thread Tools Display Modes
February 29th, 2016, 06:01 AM   #1
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Algorithm 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=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.
mobel is offline  
 
February 29th, 2016, 09:15 AM   #2
Newbie
 
Joined: Sep 2014
From: Portland, Oregon

Posts: 15
Thanks: 8

Math Focus: Number Theory
I think you'd need more discussion of expectations around how long it takes to find your examples. Try it with something not tiny like 10000# (it's less than 4300 digits so not very large).

Compare to methods of Maurer and Shawe-Taylor. They also have search steps, though using Pocklington or similar BLS75 methods. They are used daily to construct 1024 to 8192 bit primes and of course work beyond that. Neither method gets close to effectively producing record size primes (ten+ million bits).
Thanks from mobel
danaj is offline  
February 29th, 2016, 10:02 AM   #3
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Thank you.
But here the goal is different.
First : I`m not trying to build a prime for cryptography purpose. Easy to retrieve it because it is built on primorials.
Second : I want more than a result. I want a proof that if some conditions are fulfilled then the number produced is certainly prime.

For #p for example you will use only prime of the size of p
Primorial 1.000.000.000.000.000 will require to test primes of 15 digits.
I`m not sure that you got the core of the method.
mobel is offline  
February 29th, 2016, 10:50 AM   #4
Newbie
 
Joined: Sep 2014
From: Portland, Oregon

Posts: 15
Thanks: 8

Math Focus: Number Theory
I understand that a crucial question was whether your method works. I didn't address that at all. I point out a counterexample below.

I was mentioning other constructive proof methods, and pointing out that the "biggest prime ever" is very large.

Let me try with 19.
19# = 9699690
a = 3114
At 47: b = 18 mod 47, c = 47-18 = 29. Both prime, both > 19.
k = 19# + 47*29 = 9701053
l = int(sqrt(k)) = 3114 which is not prime
We can be sure than k = 9701053 is a certified prime. But k = 563 * 17231.
Thanks from mobel
danaj is offline  
February 29th, 2016, 11:19 AM   #5
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by danaj View Post
I understand that a crucial question was whether your method works. I didn't address that at all. I point out a counterexample below.

I was mentioning other constructive proof methods, and pointing out that the "biggest prime ever" is very large.

Let me try with 19.
19# = 9699690
a = 3114
At 47: b = 18 mod 47, c = 47-18 = 29. Both prime, both > 19.
k = 19# + 47*29 = 9701053
l = int(sqrt(k)) = 3114 which is not prime
We can be sure than k = 9701053 is a certified prime. But k = 563 * 17231.
Thank you for your counterexample.
It will help me for sure to more to fix the conditions required such as the number produced will be prime for sure.
Maybe there is a theoretical flaw to fix.
mobel is offline  
February 29th, 2016, 12:29 PM   #6
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Observation :
When you take #19+29 is divisible by 47
9699719=47*206377
and 206377 is divisible by 47 again
but #19+47 is not divisible by 29

Maybe I need more conditions to improve my idea.
Still thinking.

Last edited by mobel; February 29th, 2016 at 12:56 PM.
mobel is offline  
March 2nd, 2016, 04:43 AM   #7
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

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.
mobel is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
algorithm, primes



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Particular primes : summed primes mobel Number Theory 2 September 21st, 2015 02:44 PM
primes and twin primes: Number between powers of 10 caters Number Theory 67 March 19th, 2014 05:32 PM
Primes Between an - bn ,always? metinsariyar Number Theory 10 May 12th, 2011 12:09 PM
# of primes billymac00 Number Theory 4 November 22nd, 2009 05:05 PM
Odd primes as nē+2 Euzenius Number Theory 3 October 14th, 2009 01:14 PM





Copyright © 2018 My Math Forum. All rights reserved.