Prime Number Proof
Moderators: gmalivuk, Moderators General, Prelates
Prime Number Proof
Being a mostly visual person i cannot actually make an algebraic proof for finding prime numbers. in the past there have been proofs that get up to 60% of the primes in a set of numbers. thats pretty good but i want a good group of mathematicians who think they can get the proof i just want to see if we can compile our knowledge to build a complete proof of an equation finding all prime numbers in a set of numbers. For the sake of this proof lets start with numbers 11000.
When a mathemetician is faced with the option of having either $20 or everlasting bliss in the afterlife which does he choose?
Spoiler:
 gmalivuk
 GNU Terry Pratchett
 Posts: 26820
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Prime Number Proof
The best we could do for such a general idea (all primes in some set) is, I believe, to use some primality testing algorithm on each member of the set.
 Xanthir
 My HERO!!!
 Posts: 5425
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Prime Number Proof
What precisely are you talking about? Something like a polynomial that spits out primes?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Prime Number Proof
Erathostenes' sieve is pretty good at finding primes in the range 1 to n.
 qinwamascot
 Posts: 688
 Joined: Sat Oct 04, 2008 8:50 am UTC
 Location: Oklahoma, U.S.A.
Re: Prime Number Proof
11000 isn't hard. The fastest algorithm is to look it up in a table.
If you want to get really big, then there isn't a great algorithm. The best known (and quite possibly the best) is to test each element separately. In general, anything having to do with prime testing is difficult to speed up. To prove anything notable, we'd probably have to be experts in number theory. If you want to improve on something at the forefront of mathematics, then it's unlikely you'll get much done at least until you start on a Ph.D. (although not impossible).
edit: Is that what that algorithm is called? I came up with it randomly on my own programming one day lol. It's pretty good and difficult to improve on.
If you want to get really big, then there isn't a great algorithm. The best known (and quite possibly the best) is to test each element separately. In general, anything having to do with prime testing is difficult to speed up. To prove anything notable, we'd probably have to be experts in number theory. If you want to improve on something at the forefront of mathematics, then it's unlikely you'll get much done at least until you start on a Ph.D. (although not impossible).
edit: Is that what that algorithm is called? I came up with it randomly on my own programming one day lol. It's pretty good and difficult to improve on.
Quiznos>Subway
Re: Prime Number Proof
qinwamascot wrote:11000 isn't hard. The fastest algorithm is to look it up in a table.
If you want to get really big, then there isn't a great algorithm. The best known (and quite possibly the best) is to test each element separately. In general, anything having to do with prime testing is difficult to speed up. To prove anything notable, we'd probably have to be experts in number theory. If you want to improve on something at the forefront of mathematics, then it's unlikely you'll get much done at least until you start on a Ph.D. (although not impossible).
edit: Is that what that algorithm is called? I came up with it randomly on my own programming one day lol. It's pretty good and difficult to improve on.
It is possible to speed up the "test all numbers from 1n for primality" by testing for "probable primes". Basically, you devise a test that will weed out most of the composite numbers quickly, leaving you with a smaller set that still contains all the primes. For example, Fermat's little theorem states that a^p = a (mod p) when p is prime and a is a member of the integers mod p, so a quick test for probable primes is to see whether a random number taken from the range 2..(p1) raised to the power p1 is congruent to 1 mod p. Having done this for all the numbers you want to test, you then just have to check the probable primes for actual primality.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
Re: Prime Number Proof
It is trivial to come up with an equation that spits out every prime number, but the reason these equations work is that evaluating them hides just as much work as finding prime numbers the hard way.
Re: Prime Number Proof
basically what i'm talking about here is more of an information share where we share our ideas about how to come up with an equation polynomial binomial or just monomial i don't really know what it will look like but something that spits out only primes and finds better than 60% of the primes in a set. its a big dream but lets see if we can make some history.
When a mathemetician is faced with the option of having either $20 or everlasting bliss in the afterlife which does he choose?
Spoiler:
 heyitsguay
 Posts: 118
 Joined: Thu Oct 16, 2008 6:21 am UTC
Re: Prime Number Proof
phi1.618 wrote:basically what i'm talking about here is more of an information share where we share our ideas about how to come up with an equation polynomial binomial or just monomial i don't really know what it will look like but something that spits out only primes and finds better than 60% of the primes in a set. its a big dream but lets see if we can make some history.
Well you're guaranteed that no polynomial will spit out just prime numbers (at least for inputs and coefficients in Q, maybe if you work in R you can pull off some sort of trick, but I don't know it). Moreover, what you're looking for basically amounts to primality testing, if I understood it correctly. There are probabilistic methods that aren't too computationally intensive that will give very probably primes, and deterministic methods that are much more difficult to compute for large integers. I doubt we will come up with something better on this forum, but maybe I'm wrong.

 Posts: 658
 Joined: Wed Oct 01, 2008 6:04 am UTC
Re: Prime Number Proof
a while ago I bothered to make a program to search for prime numbers, written in python
it stores them in 50 MB files
anyway, to the point
I have 488MB of primes, going up to 923915747; you could try running these against some kind of pattern recognition software, but I think it would have been done before (with SUPER COMPUTERS)
anywqay all the numbers fit into a 48MB 7z file if anybody is interested
it stores them in 50 MB files
anyway, to the point
I have 488MB of primes, going up to 923915747; you could try running these against some kind of pattern recognition software, but I think it would have been done before (with SUPER COMPUTERS)
anywqay all the numbers fit into a 48MB 7z file if anybody is interested
 Cosmologicon
 Posts: 1806
 Joined: Sat Nov 25, 2006 9:47 am UTC
 Location: Cambridge MA USA
 Contact:
Re: Prime Number Proof
ConMan wrote:It is possible to speed up the "test all numbers from 1n for primality" by testing for "probable primes". Basically, you devise a test that will weed out most of the composite numbers quickly, leaving you with a smaller set that still contains all the primes.
Actually, that's not any faster than testing the numbers individually, because you'd do the same thing if you were testing them individually anyway.
The question as I see it is, if your best prmality test works in 1 millisecond for one number, is there any way to test 1000 random numbers in less than 1 second? And I think the answer is probably no.
If you know something about the numbers (for instance if they're consecutive) then you can maybe use a sieve or something. But applying a probable prime test doesn't help, because you can do it for one number just as easily as for 1000.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prime Number Proof
Probably the best visual representation of primes that there is out there right now is Sack's spiral.
http://en.wikipedia.org/wiki/Sacks_spiral
You can see some curves on that, which correspond to prime rich formula, like n^{2} + n +41.
I don't think what you actually described wanting is out there though, and sharing info isn't going to change that imo.
edit: better link
http://www.numberspiral.com/
http://en.wikipedia.org/wiki/Sacks_spiral
You can see some curves on that, which correspond to prime rich formula, like n^{2} + n +41.
I don't think what you actually described wanting is out there though, and sharing info isn't going to change that imo.
edit: better link
http://www.numberspiral.com/
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prime Number Proof
Primes also fascinate me, and there is an easy way to find one  just divide by all smaller integers. Still, it raises the question, how are integers distinct from reals? Are reals actually real or just a convenient notation, and integers are the only true representation of reality? Does reality actually deal with nonintegers at all, or is it purely the realm of abstract mathematical thought? Does pi exist in reality, or is it just a figment of imagination, a concept that is only ever approximated, never actualised? How can there be fractions of an atom, or a subatomic particle, or a quark? Is it just that the closer we look, the more we see, or is there an abstraction that covers reality in a closed form? Primes spin off a huge amount of questions, more than a concrete noninfinite test for primality can answer. I'm fascinated.
Re: Prime Number Proof
phi1.618 wrote:basically what i'm talking about here is more of an information share where we share our ideas about how to come up with an equation polynomial binomial or just monomial i don't really know what it will look like but something that spits out only primes and finds better than 60% of the primes in a set. its a big dream but lets see if we can make some history.
well "i want to believe" that there is a certain way of determining prime numbers precisely; but i doubt that it can be found in a forum . I mean you talk about sharing our knowledge; but you see all people here already have the same knowledge on ways of determining prime numbers. It's not likely that us  a bunch of smart people  will suddenly come up with a new theorem (WOOW!!). Sorry to say this; but i thought someone had to write it.
But in any case, if you "make some history"; i would be very proud that i have replied a post of a famous Mathematician. It would be like "Erdos number"; only it would be called "phi1.618 number".
Now I understand why 42 is the answer to life, the universe, and everything. See, it means a 7 on all IB subjects. (excluding the 3 bonus points, of course)
 MartianInvader
 Posts: 809
 Joined: Sat Oct 27, 2007 5:51 pm UTC
Re: Prime Number Proof
Cosmologicon wrote:ConMan wrote:The question as I see it is, if your best prmality test works in 1 millisecond for one number, is there any way to test 1000 random numbers in less than 1 second? And I think the answer is probably no.
If you know something about the numbers (for instance if they're consecutive) then you can maybe use a sieve or something. But applying a probable prime test doesn't help, because you can do it for one number just as easily as for 1000.
Well I think the answer to your phrasing of the question is actually yes, because if answering "Is it prime?" takes 1 millisecond, then answering, say, "It is divisible by 2?" would presumably take a lot less time. So if you start with an array of 1000 numbers, then sieve it (go through and get rid of all even numbers, then all multiples of 3, etc.), it will be a lot faster than testing each number individually. You are still hitting each number, so in bigO notation you might not be any faster, but the fact that you can rule out numbers faster than it takes to run a primality test on each one makes things a bit faster.
On the other hand, if you meant "The primality test takes an AVERAGE of 1 millisecond", then sieving probably wouldn't help. Though if you could implement the sieve in a really clever way, for example if it could quickly figure out which number to jump to next for testing without having to go through them one by one, then you might have something.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!
Re: Prime Number Proof
phi1.618 wrote:basically what i'm talking about here is more of an information share where we share our ideas about how to come up with an equation polynomial binomial or just monomial i don't really know what it will look like but something that spits out only primes and finds better than 60% of the primes in a set. its a big dream but lets see if we can make some history.
Before making history it is usually wise to study it. See:
http://mathworld.wolfram.com/PrimeDioph ... tions.html
http://mathworld.wolfram.com/PrimeGene ... omial.html
http://mathworld.wolfram.com/PrimeFormulas.html
http://en.wikipedia.org/wiki/Formula_for_primes
Re: Prime Number Proof
i kind of just started a conversation i didnt want to start some kind of "it cant be done thing. whatever if you wanna share some cool facts about primes go for it.
When a mathemetician is faced with the option of having either $20 or everlasting bliss in the afterlife which does he choose?
Spoiler:
Re: Prime Number Proof
Well, what I do is take the square root of a number and check it for all primes less than that.
I mean, let's say we have 599. (599)^(1/2) = 24.4...
So, counting down, 23 is prime, 19 is prime, 17, 13, 11, 7, 5, 3...
and since it all divides out to messy, non whole numbers, we can say it is prime.
I mean, let's say we have 599. (599)^(1/2) = 24.4...
So, counting down, 23 is prime, 19 is prime, 17, 13, 11, 7, 5, 3...
and since it all divides out to messy, non whole numbers, we can say it is prime.
Re: Prime Number Proof
The product of n sequential primes +1 is relatively prime to all integers [imath]\leq[/imath] n (hmm, why didn't TeX work? because your slash went the wrong way  gm), however, there are plenty of unknown primes, this doesn't work as an iterative process and the product + 1 may have integer parts > n.
Counter Examples:
(2) + 1 = 3
(2 * 3) + 1 = 7
(2 * 3 * 7) + 1 = 43
(2 * 3 * 7 * 43) + 1 = 1,807 which is composite (13 divides it)
(2 * 3 * 5 * 7 * 11 * 13) + 1 = 30,031 (59 divides it)
Counter Examples:
(2) + 1 = 3
(2 * 3) + 1 = 7
(2 * 3 * 7) + 1 = 43
(2 * 3 * 7 * 43) + 1 = 1,807 which is composite (13 divides it)
(2 * 3 * 5 * 7 * 11 * 13) + 1 = 30,031 (59 divides it)
Last edited by gmalivuk on Sun Dec 07, 2008 8:29 pm UTC, edited 1 time in total.
Reason: fixed TeX
Reason: fixed TeX
Re: Prime Number Proof
So the idea is that you sit back and relax and some mathematicians in here create a formula for you that is deemed impossible to produce.
This script produces the first million primes in 110seconds on my laptop and saves them to disk. It uses sieve of Eratosthenes and tests with modulo for prime factors until the square of the factor is greater than the tested number.
I think it's pretty fast but any ideas on how to make it faster?
CODE:
This script produces the first million primes in 110seconds on my laptop and saves them to disk. It uses sieve of Eratosthenes and tests with modulo for prime factors until the square of the factor is greater than the tested number.
I think it's pretty fast but any ideas on how to make it faster?
CODE:
Spoiler:
Re: Prime Number Proof
HNSZ wrote:This script produces the first million primes in 110seconds on my laptop and saves them to disk. It uses sieve of Eratosthenes and tests with modulo for prime factors until the square of the factor is greater than the tested number.
I think it's pretty fast but any ideas on how to make it faster?
This comes up often. Short answer:
http://forums.xkcd.com/viewtopic.php?f=11&t=27193&p=873100#p873100
Long answer:
http://forums.xkcd.com/viewtopic.php?f=12&t=30707&p=1008901#p1008901
Re: Prime Number Proof
jaap wrote:This comes up often.
Yeah I know primes are popular. Thanks for your reply but my version already uses the suggested methods so it's either faster or as fast as the linked versions.
Re: Prime Number Proof
HNSZ wrote:jaap wrote:This comes up often.
Yeah I know primes are popular. Thanks for your reply but my version already uses the suggested methods so it's either faster or as fast as the linked versions.
I don't think so. It seems to me as if your code builds a list, extending it by using trial division using the previously found primes. You should find the primes without using division (or mod) at all, only addition.
Start with a list of booleans, all set to true. Then set every second one to false (starting with 4) to cross off all multiples of 2. Then set every third one to false (starting with 6) to cross off all multiples of 3. And so on. There is no / or % in that algorithm.
I've done that in Java, and it produces all primes under 50 million in a second.
Re: Prime Number Proof
jaap wrote:Start with a list of booleans, all set to true. Then set every second one to false (starting with 4) to cross off all multiples of 2. Then set every third one to false (starting with 6) to cross off all multiples of 3. And so on. There is no / or % in that algorithm.
I've done that in Java, and it produces all primes under 50 million in a second.
EDIT
Ahum, never mind. Good point.
The only downside would be that it needs to know how many you need up front, but it would definitely be way faster.
Re: Prime Number Proof
It's true, the quick implementation I did in java tossed out 1m primes in 168 millis, the full 50m took about 2.5 seconds for me.
That said, is there an efficient algorithm for extending a list of primes? Say I had all primes Under 1m, but I later discovered I need all primes under 2m. With these size numbers it's almost trivial to just start over and run the sieve again, but if I have to extend it several times it starts to seem horribly inefficient. I've tried a few obvious methods, including starting the seive over, but seeding it with my prime list. I'm not sure if the implementation was poor or what, but it turned out not to be too terribly much faster.
That said, is there an efficient algorithm for extending a list of primes? Say I had all primes Under 1m, but I later discovered I need all primes under 2m. With these size numbers it's almost trivial to just start over and run the sieve again, but if I have to extend it several times it starts to seem horribly inefficient. I've tried a few obvious methods, including starting the seive over, but seeding it with my prime list. I'm not sure if the implementation was poor or what, but it turned out not to be too terribly much faster.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.
Galileo
Galileo
Who is online
Users browsing this forum: No registered users and 10 guests