 mersenneforum.org Is there a Prime prediction algorithm?
 Register FAQ Search Today's Posts Mark Forums Read 2007-02-21, 12:55 #1 Omniprime1   Feb 2007 3 Posts Is there a Prime prediction algorithm? Is there a Prime prediction algorithm?   2007-02-21, 13:34   #2
T.Rex

Feb 2004
France

929 Posts Quote:
 Originally Posted by Omniprime1 Is there a Prime prediction algorithm?
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 2007-02-21 at 13:34   2007-02-21, 15:03   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

5×1,493 Posts Quote:
 Originally Posted by Omniprime1 Is there a Prime prediction algorithm?
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?

Are you perhaps asking whether a function exists that can calculate
the n'th prime given n? Again, the answer is yes.   2007-02-21, 18:38   #4
Omniprime1

Feb 2007

310 Posts Quote:
 Originally Posted by R.D. Silverman Your question is not well posed. What do you mean by "prime 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.
I mean to be able to PREDICT the next prime number in a sequence and ELIMINATE many NUMBERS THAT WOLD NOT BE PRIME in advance. Without having to SEARCH the squence space.

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 2007-02-21 at 18:54   2007-02-21, 19:24   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

5·1,493 Posts Quote:
 Originally Posted by Omniprime1 I mean to be able to PREDICT the next prime number in a sequence and ELIMINATE many NUMBERS THAT WOLD NOT BE PRIME in advance.
(1) You don't have to shout.

(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 [(1-epsilon)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.   2007-02-21, 19:34   #6
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts Quote:
 Originally Posted by R.D. Silverman If you want to discuss mathematics, you need to learn the language of mathematics.

Alex   2007-02-21, 19:47   #7
Omniprime1

Feb 2007

112 Posts Quote:
 Originally Posted by akruppa But what about Miscellaneous Mathematics? Alex
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 2007-02-21 at 19:53   2007-02-21, 19:50 #8 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts Yep, that's the language of Miscellaneous Math. Welcome on board! Alex   2007-03-01, 20:04   #9
m_f_h

Feb 2007

1101100002 Posts Quote:
 Originally Posted by R.D. Silverman 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. (...) 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.
I suppose this (i.e. the function nextprime(x)) was indeed the intended meaning of "predict in advance".
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 pseudo-primality 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^N-1, i.e. all N binary digits =1.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post hpersaud Miscellaneous Math 3 2016-06-16 10:15 Jonathan Data 3 2015-07-03 01:27 paulunderwood 3*2^n-1 Search 7 2008-06-20 10:31 Visu Math 66 2008-05-12 13:55 Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 05:00.

Sat Aug 20 05:00:37 UTC 2022 up 2 days, 2:29, 0 users, load averages: 1.46, 1.24, 1.20