• Advertisement

Archived

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

Primes

This topic is 5488 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
Any composite number N has a divisor less than or equal to sqrt(N) so you don''t have to test every single number, but still a whole lot of them.

Someone recently discovered an "efficient" primality test. I say "efficient" because although its complexity is polynomial it''s still EXTREMELY slow for large primes.

Share this post


Link to post
Share on other sites
I don''t think you can corner the market on memory for $100k. I could be wrong, but isn''t log(log(10^10^6))=6? So even if that was only bytes does the world even have 1/6*10^1000000 bytes of memory. Say the average computer had 10^10 bytes of memory, every person had 10^5 computers and you had 10^10 people then you would only have 3/20000th of the memory you would need.

Sorry, spending too much time around engineers.

Share this post


Link to post
Share on other sites
Couldn''t you re-use memory from the first 300,000,000 to calculate the second batch?

I suppose there''s a way to overlap the numbers in memory, to save all the preceding zeros.

Also, since all but one of the primes is odd, the lowest bit can be assumed to be one, and discarded. After you''ve calculated 300,000,000 primes, you can free up enough space to store another number up to 2^300000000

********


A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Share this post


Link to post
Share on other sites
Prime Info

Hey, I just started playing around with primes myself. Hope some of this site's info will be useful to some people here.

Good Luck finding a 100% proven why of generating huge primes quickier then modern methods.;P

the cheesy algo for finding the small primes I use is:


    
// primes array is global with 8000 element max for now


unsigned char PG_Primes_Squared(unsigned long int max_number, unsigned char Flag_MakeFile)
{
unsigned long int i,j,square_root,prime_squared;
unsigned long int primes_found=0;
FILE *fptr_primes=0;

// Create/Override File

if(!(fptr_primes=fopen("primes.txt","w+t")))
{// File was not created

printf("\n\n!!!File could not be created!!!\n\n");
printf("\n\nPress a key to exit...\n");
getch();
return(0);
}

// put the first two known primes in the list

fprintf(fptr_primes,"List of Primes\n---------------\n");
primes[0]=2;primes[1]=3;
primes_found=2;

// generate the primes

prime_squared = primes[1] * primes[1];
square_root = 1;
for(i=5;i<=max_number;i+=2) // only step through the odds

{

// when the numbers become greater than the currently used squared prime use the next

if(prime_squared<i)
{square_root++;
prime_squared = primes[square_root] * primes[square_root];
printf(".");
}

// using the square of the primes to limit the tested primes

j=1; // no need to divide by 2 because only odds are tested

while((j<=square_root)&&(i%primes[j]!=0)){j++;}

// Check if prime was found

// basically if (j-1 == square_root) then the number couldn't be divided

// by the primes

if((--j)==square_root)
{//prime was found

if(primes_found<8000){primes[primes_found] = i;}
primes_found++;
}
}

// Print the primes into the file

if(Flag_MakeFile)
{
for(i=0;i<primes_found;i++)
{
if(i<8000){fprintf(fptr_primes,"%u]. %u\n",i+1,primes[i]);}
}
}

// Display results

printf("\n\nResults\n--------\n");
printf(" %u Primes found.\n Largest prime used to factor was %u. The %uth prime found.\n",primes_found,primes[square_root],square_root+1);
printf("\n");

// End of PG_Primes_Squared

fclose(fptr_primes);
return(1);
}


Primes can be fun to fight with looking for crazy patterns and certainties. Someday I hope to understand enough to make some sort of contribution to the discovery of huge primes.

[edited by - CodeJunkie on February 8, 2003 6:46:29 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually, the price is for a 10 million digit prime. A 4 million digit prime has already been found (2^13466917-1).

Share this post


Link to post
Share on other sites
Going back to the original, let Pn be the highest found prime

The product of all primes up to Pn, plus one, is either prime or the product of much larger primes.

let An be the product of the first n primes, and B be P(n+1)

A(n+1)=An*P(n+1)
P(n+2)=A(n+1)+1

Since this only requires memory for storing 2 numbers, there shouldn''t be a problem finding Pm 10 million digits long. Since Pm is likely to be prime, won''t this be a relativly fast, considering many primes are skipped?

********


A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
walkingcarcass, watch out for your signature

Share this post


Link to post
Share on other sites

  • Advertisement