mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2007-02-21, 12:55   #1
Omniprime1
 
Feb 2007

3 Posts
Default Is there a Prime prediction algorithm?

Is there a Prime prediction algorithm?
Omniprime1 is offline   Reply With Quote
Old 2007-02-21, 13:34   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91410 Posts
Default

Quote:
Originally Posted by Omniprime1 View Post
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
T.Rex is offline   Reply With Quote
Old 2007-02-21, 15:03   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by Omniprime1 View Post
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?

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.
R.D. Silverman is offline   Reply With Quote
Old 2007-02-21, 18:38   #4
Omniprime1
 
Feb 2007

112 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
Omniprime1 is offline   Reply With Quote
Old 2007-02-21, 19:24   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by Omniprime1 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-02-21, 19:34   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
If you want to discuss mathematics, you need to learn the language
of mathematics.
But what about Miscellaneous Mathematics?

Alex
akruppa is offline   Reply With Quote
Old 2007-02-21, 19:47   #7
Omniprime1
 
Feb 2007

3 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
Omniprime1 is offline   Reply With Quote
Old 2007-02-21, 19:50   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

Yep, that's the language of Miscellaneous Math. Welcome on board!

Alex
akruppa is offline   Reply With Quote
Old 2007-03-01, 20:04   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Yet Another Prime Listing Algorithm hpersaud Miscellaneous Math 3 2016-06-16 10:15
A Mersenne Prime Algorithm for Children Jonathan Data 3 2015-07-03 01:27
Prediction for the next prime paulunderwood 3*2^n-1 Search 7 2008-06-20 10:31
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 22:19.

Fri Oct 23 22:19:09 UTC 2020 up 43 days, 19:30, 0 users, load averages: 1.49, 1.68, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.