Prime Number Proof

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
phi1.618
Posts: 6
Joined: Mon Dec 01, 2008 4:54 am UTC

Prime Number Proof

Postby phi1.618 » Wed Dec 03, 2008 12:13 am UTC

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 1-1000.
When a mathemetician is faced with the option of having either $20 or everlasting bliss in the afterlife which does he choose?
Spoiler:
The $20 because nothing is better than everlasting bliss in the afterlife and $20 is better than nothing

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26820
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Prime Number Proof

Postby gmalivuk » Wed Dec 03, 2008 12:23 am UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Xanthir
My HERO!!!
Posts: 5425
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Prime Number Proof

Postby Xanthir » Wed Dec 03, 2008 12:28 am UTC

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)))

User avatar
GBog
Posts: 114
Joined: Fri Jun 01, 2007 4:57 pm UTC

Re: Prime Number Proof

Postby GBog » Wed Dec 03, 2008 12:32 am UTC

Erathostenes' sieve is pretty good at finding primes in the range 1 to n.

User avatar
qinwamascot
Posts: 688
Joined: Sat Oct 04, 2008 8:50 am UTC
Location: Oklahoma, U.S.A.

Re: Prime Number Proof

Postby qinwamascot » Wed Dec 03, 2008 12:34 am UTC

1-1000 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.
Quiznos>Subway

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Prime Number Proof

Postby ConMan » Wed Dec 03, 2008 4:28 am UTC

qinwamascot wrote:1-1000 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 1-n 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..(p-1) raised to the power p-1 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:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Prime Number Proof

Postby t0rajir0u » Wed Dec 03, 2008 4:37 am UTC

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.

User avatar
phi1.618
Posts: 6
Joined: Mon Dec 01, 2008 4:54 am UTC

Re: Prime Number Proof

Postby phi1.618 » Wed Dec 03, 2008 5:03 am UTC

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:
The $20 because nothing is better than everlasting bliss in the afterlife and $20 is better than nothing

User avatar
heyitsguay
Posts: 118
Joined: Thu Oct 16, 2008 6:21 am UTC

Re: Prime Number Proof

Postby heyitsguay » Wed Dec 03, 2008 7:26 am UTC

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.

keeperofdakeys
Posts: 658
Joined: Wed Oct 01, 2008 6:04 am UTC

Re: Prime Number Proof

Postby keeperofdakeys » Wed Dec 03, 2008 8:42 am UTC

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

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Prime Number Proof

Postby Cosmologicon » Wed Dec 03, 2008 9:07 am UTC

ConMan wrote:It is possible to speed up the "test all numbers from 1-n 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.

User avatar
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

Postby jestingrabbit » Wed Dec 03, 2008 11:08 am UTC

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 n2 + 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.

nazlfrag
Posts: 44
Joined: Sun Nov 09, 2008 2:54 pm UTC
Location: Australia
Contact:

Re: Prime Number Proof

Postby nazlfrag » Wed Dec 03, 2008 1:32 pm UTC

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 non-integers 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 non-infinite test for primality can answer. I'm fascinated.

User avatar
nerd1729
Posts: 6
Joined: Sun Nov 30, 2008 6:45 pm UTC

Re: Prime Number Proof

Postby nerd1729 » Wed Dec 03, 2008 3:07 pm UTC

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)

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Prime Number Proof

Postby MartianInvader » Wed Dec 03, 2008 5:29 pm UTC

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 big-O 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!

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Prime Number Proof

Postby t0rajir0u » Thu Dec 04, 2008 9:23 pm UTC

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/Prime-Gene ... omial.html
http://mathworld.wolfram.com/PrimeFormulas.html
http://en.wikipedia.org/wiki/Formula_for_primes

User avatar
phi1.618
Posts: 6
Joined: Mon Dec 01, 2008 4:54 am UTC

Re: Prime Number Proof

Postby phi1.618 » Fri Dec 05, 2008 2:58 am UTC

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:
The $20 because nothing is better than everlasting bliss in the afterlife and $20 is better than nothing

Rentsy
Posts: 154
Joined: Tue Dec 02, 2008 4:13 am UTC

Re: Prime Number Proof

Postby Rentsy » Fri Dec 05, 2008 4:12 am UTC

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.

chapel
Posts: 121
Joined: Mon Dec 01, 2008 8:52 am UTC

Re: Prime Number Proof

Postby chapel » Fri Dec 05, 2008 8:57 am UTC

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)
Last edited by gmalivuk on Sun Dec 07, 2008 8:29 pm UTC, edited 1 time in total.
Reason: fixed TeX

HNSZ
Posts: 10
Joined: Fri Dec 05, 2008 9:22 am UTC

Re: Prime Number Proof

Postby HNSZ » Fri Dec 05, 2008 9:39 am UTC

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:
Spoiler:

Code: Select all

# Prime generator
import sys
import time



primelist = []
class Primes:
   filename = 'primes.csv'
   fp = 0
   file_present=True
   prime_list = []
   file_primes = 0
   file_size = 0
   def __init__(self):
      self.file_primes = self.init_prime_from_file()
   def save_primes(self):
      if len(self.prime_list) > self.file_size:
         try:
            fp =  open(self.filename, 'w')
         except:
            return False
         for p in self.prime_list:
            fp.write(str(p))
            fp.write(",")
         fp.close()
      else:
         return False
   def get_prime(self):
      if self.file_present == True:
         p = self.file_primes.next()
         if p != False:
            self.file_size += 1
            self.add(p)
            return p
         else:
            self.file_present = False
      if len(self.prime_list) == 0:
         self.add(2)
         return 2         
      p = self.prime_list[-1]
      if p == 2:
         self.add(3)
         return 3
         
      p += 2
      while self.is_prime(p) == False:
         p += 2
      return p
   def init_prime_from_file(self):
      try:
         fp = open(self.filename, 'r')
         value=''
         for char in fp.read():
            if char == ',':
               yield int(value)
               value=''
            else:
               value += char
         fp.close()
         yield False
      except:
         yield False
   def is_prime(self, number):
      for p in self.prime_list:
         if number % p == 0 :
            return False
         if p*p >= number:
            self.add(number)
            return True
            
      divider = p
      while divider * divider <= number:
         if number % divider == 0:
            return False
         divider += 2

      self.add(number)
      return True
   def add(self,prime):
      self.prime_list.append(prime)

print "I make primes, how many do you want?",      
n = int(raw_input())
primes = Primes()
i = 0

start = time.time()
while i < n:
   p = primes.get_prime()
   i+=1
   
end = time.time()
print "The %dth prime is: %d" % (i,p)
print "Time:", end-start
if primes.save_primes() != False:
   print "The primes have been saved in the file:", primes.filename

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Prime Number Proof

Postby jaap » Fri Dec 05, 2008 9:58 am UTC

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

HNSZ
Posts: 10
Joined: Fri Dec 05, 2008 9:22 am UTC

Re: Prime Number Proof

Postby HNSZ » Fri Dec 05, 2008 12:47 pm UTC

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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Prime Number Proof

Postby jaap » Fri Dec 05, 2008 1:29 pm UTC

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.

HNSZ
Posts: 10
Joined: Fri Dec 05, 2008 9:22 am UTC

Re: Prime Number Proof

Postby HNSZ » Fri Dec 05, 2008 2:23 pm UTC

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.

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Prime Number Proof

Postby spdqbr » Fri Dec 05, 2008 3:26 pm UTC

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.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests