20070221, 12:55  #1 
Feb 2007
3 Posts 
Is there a Prime prediction algorithm?
Is there a Prime prediction algorithm?

20070221, 13:34  #2 
Feb 2004
France
929 Posts 
There are some tests that can say if a number has a high probability to be prime or not. But then you have to run another test which provides the proof that the number is prime. So, predicting may mean running probabilistic tests and get a positive (close to 100% sure, but never 100%) answer, I guess.
T. Last fiddled with by T.Rex on 20070221 at 13:34 
20070221, 15:03  #3 
"Bob Silverman"
Nov 2003
North of Boston
5×1,493 Posts 
Your question is not well posed.
What do you mean by "prime betrig prediction algorithm"? In particular, the word "predict" is totally vague. What does it mean to "predict" a prime? Do you mean: Is there an algorithm which, given a specific prime, can find the next prime? The answer is certainly. Are you perhaps asking whether a function exists that can calculate the n'th prime given n? Again, the answer is yes. Please be more specific. 
20070221, 18:38  #4  
Feb 2007
3_{10} Posts 
Quote:
And/or at least predict the smallest field space possible in which the next prime will be found. (Where to look in the sequence) Imagine an infinite sequence of dots, in projecting out as a geometric series (whole numbers) equidistant from one another, now imagine looking at those dots and eliminating the lines of dots (i.e. numbers) *automatically* and leaving behind all prime numbers, at a glance. Without having to test if the number is prime, because you can see that it is. Last fiddled with by Omniprime1 on 20070221 at 18:54 

20070221, 19:24  #5  
"Bob Silverman"
Nov 2003
North of Boston
5·1,493 Posts 
Quote:
(2) You still have not defined what you mean by "predict". "predict" is not a well defined mathematical concept. (3) The expression "in advance" is also not well defined. In advance of what? In advance of doing any computation at all? That is clearly impossible. If you want to discuss mathematics, you need to learn the language of mathematics. If you mean: "given a prime p_n", determine p_{n+1} as a function of p_n, then the answer is yes. This can be done. But the function will be hard to compute, in a strict technical sense (i.e. requires exponentiial time as a function of the size of p_n). " On the other hand, one can give an algorithm that runs in polynomial time as a function of the size of p_n. This algorithm does eliminate most (but not all) of the numbers in the interval (say) [p_n, p_n + log^2(p_n)] without testing them for primaility. It does so with a sieve. One then tests the remaining numbers with a prime testing algorithm. Given a prime p_n, the next prime, on average, will be approximately p_n + log(p_n). But this is an *average* for the set of primes in the interval [(1epsilon)p_n, (1+epsilon)p_n]. For any given p_n, the next prime might be p_n + 2, or it might be p_n + floor(log^2 p_n). The gaps between primes are not uniform, nor do we have a proof that they follow any specific statistical distribution. 

20070221, 19:34  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 

20070221, 19:47  #7 
Feb 2007
11_{2} Posts 
The language of math is the world, math is just abstractalization of things in nature, and nature is physicalization of things in math.
It is a set union or perhaps a reflection, one is in one form, another is in another form. The "language of math" is limited by the numeric system used, of which there are many, what abou a visual numeric system based on geometry and/or shapes? Anyways I'll try to explain in a clear manner with a picture of what I've been thinking... I will upload in a while. Last fiddled with by Omniprime1 on 20070221 at 19:53 
20070221, 19:50  #8 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Yep, that's the language of Miscellaneous Math. Welcome on board!
Alex 
20070301, 20:04  #9  
Feb 2007
110110000_{2} Posts 
Quote:
However, even if that function is quite fast for quite big numbers, I think you're not close to winning the prize money by just typing > nextprime( 10^(10^7)); into your Maple worksheet: It's just because this number 10^10^7 is not just very big, but rather huge. I think you would already win some prize money (and some big academic distinction if not the fields medal) if you could give an efficient pseudoprimality test for numbers of that size. (They have about 10^7 log(2)/log(10) > 30 ooo ooo binary digits and thus make up a 4 Mb file if stored as such. If there was a reasonable method to know if such a number was composite, even if it's only to 1/1000 accurate or a bit better, I am sure that GIMPS software would (at least YOU should!) use this test instead of trial factoring (i.e. trying to find a "small factor" of < 2^70) which already takes a day or so, before starting the LL test. Even better : It's sufficient if your method gives such an answer for the very simple numbers 2^N1, i.e. all N binary digits =1. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Yet Another Prime Listing Algorithm  hpersaud  Miscellaneous Math  3  20160616 10:15 
A Mersenne Prime Algorithm for Children  Jonathan  Data  3  20150703 01:27 
Prediction for the next prime  paulunderwood  3*2^n1 Search  7  20080620 10:31 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 