Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

walkingcarcass

Primes

This topic is 5669 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

this is a pre-emptive *not* homework statement. Suppose I have a list of the first N primes of which the last one is P Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1 the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one are there any prime numbers between P and Q? ******** A Problem Worthy of Attack Proves It''s Worth by Fighting Back

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
N=2
P=3

Q=2*3 + 1 = 7
between P=3 and Q=7 there is 5

Share this post


Link to post
Share on other sites
There has to be because of some theorem that I think is called Bertrand's Posulate, saying that for all P prime, there exists a prime between P and 2P. The proof of this is very complex, and I think Erdos has one of the simplest proofs that he came up with when he was in his late teens. Since P in your expression is multipled by every prime before that, and every other prime is greater than 2, I think that by this theorem there are at least N primes, where N is the number of primes up to P, between Q and P.

Brendan


[edited by - Punty50 on February 7, 2003 12:00:14 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by walkingcarcass
Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1
the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one



Err... Nope.

2*3*5*7*11*13 + 1 = 30031 = 59*509

Share this post


Link to post
Share on other sites
I''m not sure where you got this setup from, but it reminds me of the proof that there are infinitely many primes... it states that if there are a finite number, then multiply them together, and add 1. Then, that must be prime, which means that there is another prime outside of the previously defined set of ALL of them, reduxio ad absurdum. But that one only works if you have ALL the primes, because every natural number can be broken down into one and only one list of primes (viz. Fundamental Theorem of Arithmetic), and therefore if it couldn''t be divided my anything in the original list (all primes), it couldn''t be a natural number, but all the closure in supposition says it would be.

Anyhow, that''s why alvaro could find a counterexample, because your lis lacks the properties I stated above. These things make a lot more sense in my head, I might come back and explain it in simpler terms later, but I wouldn''t count on it ;-).

Share this post


Link to post
Share on other sites
Yeah, it doesn''t work all the time.
But the reason it works a lot of the time is because
whenever you have a list of primes p1...pn and
a number r that is relatively prime to all these numbers,
(the product of primes(p1...pn))+r can be prime.
In fact, all primes can be expressed in this way. I developed
a prime-number-finding algorithm based on this discovery.
The running time of my algorithm is O(n/log(log(n))).
That''s sub-linear! So in theory, you could find all the primes
up to n in less than n steps. The running time assumes
I have access to an oracle that computes arithmetic
operations such as multiplication and division in unit time,
regardless of the size of the numbers. The trick in the algorithm
is how I eliminate the composite numbers generated by the
formula above. The bad part of the algorithm is that it requires
O(n/log(log(n))) memory (where a unit of memory can hold
an arbitrarily large number no greater than n). So I''ve
only been able to generate all primes up to about 300,000,000.
After that, I run out of memory.


Steven Borkman
Home Page: http://www.borkman.mygamesite.net
Video Game Page: http://www.dev.mygamesite.net

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
2*3*5*7*11*13 + 1 = 30031 = 59*509


the prrof says that the result must either be a prime number OR can be divided by a new prime number that was not in the original list of prime numbers used.

Share this post


Link to post
Share on other sites
quote:
Original post by alvaro
[quote]Original post by walkingcarcass
Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1
the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one



Err... Nope.

2*3*5*7*11*13 + 1 = 30031 = 59*509



That''s because the actual theorem is: either the result is prime or it is a multiple of a prime larger than P. In this case it is a multiple of 59, a prime larger than 13.

8 billion HTTP 500 errors....

Share this post


Link to post
Share on other sites
Yeah, same thing, it''s outside the set, and it''s larger, you''re both right, it''s just always larger in this case because we''re starting at zero and not skipping any.

About that algorithm though... very interesting, you know there''s a contest on to find ridiculously large primes, if you can get one with I think 1 million decimal digits, they''ll award you 100 grand. Might be worth the investment if you KNOW you could do it with more memory.

Share this post


Link to post
Share on other sites
Is there actually an algorithm to definitively prove you have a prime (other than just trying every possiblility upto the number in question)...I understood that there are no perfect algorithms for this

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!