Ok just so someone might possibly figure them out also before I spoil primes for everyone... So... Go head and try to figure primes out you got a lil bit before ill spoil. BTW its really easy to pwn primes sad you all couldnt do it yet.
Lifetime ban if you have failed to do this.
Its going to be really good rpenner. Your going to feel terribly upset when I show you how it was done.
Should we set a deadline then?
Magpies next post has to have it.
Should I start popping some corn?
I mean seeing the solution to primes, should be entertaining.
I mean seeing the solution to primes, should be entertaining.
Oh goodie goodie....
Ok so here is how primes are solved folks.
Instead of brute force solving a number to see if its prime... Instead brute force the numbers to see if they are not prime. We know primes have to come together to some degree so all you need to do is find the numbers that cant be prime and then you can narrow the possible prime numbers down by elimination. The reason this is primes solved is because the only way you can find primes is brute force really... You can guess and then brute force thats it. However if your trying to find numbers that are not prime the job becomes much easyer. Like most of the numbers that could be prime that arnt prime will be divisible by 3 right away and some might take a lil bit longer to crack but not anywhere near as long as it does to find a prime thru brute force.
So there you have it my primes solved
Egg on the face of anyone who has ever cracked a high prime number by brute force without just checking the numbers around it first I mean if you actualy find a large prime the last thing you should ever do is brute force it right? Thats like dividing it 50,000 times just to be sure when you could just divide the numbers around it like 20 each...
Instead of brute force solving a number to see if its prime... Instead brute force the numbers to see if they are not prime. We know primes have to come together to some degree so all you need to do is find the numbers that cant be prime and then you can narrow the possible prime numbers down by elimination. The reason this is primes solved is because the only way you can find primes is brute force really... You can guess and then brute force thats it. However if your trying to find numbers that are not prime the job becomes much easyer. Like most of the numbers that could be prime that arnt prime will be divisible by 3 right away and some might take a lil bit longer to crack but not anywhere near as long as it does to find a prime thru brute force.
So there you have it my primes solved
Egg on the face of anyone who has ever cracked a high prime number by brute force without just checking the numbers around it first I mean if you actualy find a large prime the last thing you should ever do is brute force it right? Thats like dividing it 50,000 times just to be sure when you could just divide the numbers around it like 20 each...
QUOTE (rpenner+Jun 19 2009, 04:57 PM)
Magpies next post has to have it.
Goodbye magpie.
You won't be missed.
Goodbye magpie.
You won't be missed.
That has got to be the best solution for primes ever... What did you think I actualy found a magical number you can always find a prime with? If you did you dont understand how primes are picked... Primes wont be solved solved even in 1000 billion years. Numbers are infinte so they have infinite complexity.
*Waves goodbye*
QUOTE (magpies+Jun 23 2009, 05:30 AM)
Instead of brute force solving a number to see if its prime... Instead brute force the numbers to see if they are not prime. We know primes have to come together to some degree so all you need to do is find the numbers that cant be prime and then you can narrow the possible prime numbers down by elimination. The reason this is primes solved is because the only way you can find primes is brute force really... You can guess and then brute force thats it. However if your trying to find numbers that are not prime the job becomes much easyer. Like most of the numbers that could be prime that arnt prime will be divisible by 3 right away and some might take a lil bit longer to crack but not anywhere near as long as it does to find a prime thru brute force.
You seem to be describing something like a prime number sieve. For instance, consider the numbers 2 to 10. The square root of 10 is 3.(something) and the primes below that are 2 and 3, so remove all multiples (other than 1) of 2 and 3 from your list of 2 to 10. That leaves 2, 3, 5, 7. They are prime.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes has more information. However, it is not a very efficient algorithm for large numbers, as the description of order complexity on the Wiki page explains.
You seem to be describing something like a prime number sieve. For instance, consider the numbers 2 to 10. The square root of 10 is 3.(something) and the primes below that are 2 and 3, so remove all multiples (other than 1) of 2 and 3 from your list of 2 to 10. That leaves 2, 3, 5, 7. They are prime.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes has more information. However, it is not a very efficient algorithm for large numbers, as the description of order complexity on the Wiki page explains.
QUOTE (magpies+Jun 23 2009, 05:30 AM)
Egg on the face of anyone who has ever cracked a high prime number by brute force without just checking the numbers around it first
This is incorrect. Suppose you want to check p is prime. Knowing p-2 and p+2 are not prime doesn't tell you if p is prime. If p-2 and p+2 are prime then p is not (divisible by 3) but you're basically saying that rather than check if p is prime why not check p-2 and p+2 are prime. That's twice the work!
QUOTE (magpies+Jun 23 2009, 05:30 AM)
I mean if you actualy find a large prime the last thing you should ever do is brute force it right?
Firstly, brute force is not the actual method used, there's nifty number theory tricks to check if something is prime which are quicker. For instance Fermat's Little Theorem can render check primality of medium sized numbers doable by hand.
All 'largest primes' for the last few decades have been of a special kind, Mersenne primes, which due to their close relation to powers of two (and thus binary) they are more easily analysed than other, general, primes. They are of the form 2^p - 1 where p is prime because if you have 2^(n*m) - 1 then you can factorise the number immediately. Otherwise you need to use the special number field sieve.
Brute force is only used when you know the numbers are so small it takes more time to write a better algorithm than would be saved by using the better algorithm.
All 'largest primes' for the last few decades have been of a special kind, Mersenne primes, which due to their close relation to powers of two (and thus binary) they are more easily analysed than other, general, primes. They are of the form 2^p - 1 where p is prime because if you have 2^(n*m) - 1 then you can factorise the number immediately. Otherwise you need to use the special number field sieve.
Brute force is only used when you know the numbers are so small it takes more time to write a better algorithm than would be saved by using the better algorithm.
QUOTE (magpies+Jun 23 2009, 05:30 AM)
That has got to be the best solution for primes ever.
No, it's actually slower.
QUOTE (magpies+Jun 23 2009, 05:30 AM)
What did you think I actualy found a magical number you can always find a prime with?.
There are prime equations.
QUOTE (magpies+Jun 23 2009, 05:30 AM)
f you did you dont understand how primes are picked... Primes wont be solved solved even in 1000 billion years. Numbers are infinte so they have infinite complexity.
Wrong on several counts. Primes seem to be random, but they do follow trends, as Gauss's formula shows. We can work out places where primes are more likely to be (such as the Mersenne primes) or where they won't be, though a precise formula doesn't yet exist. The Riemann hypothesis can be related to primes and if a proof to that is found then it might lead to a high speed or general factorising algorithm, making primes 'understood'. Also, just having infinitely many terms in a sequence doesn't mean it's infinitely complex. There's infinitely many even numbers, but they are all of the form 2n, that's not 'infinitely complex'.
Noone is trying to list every single prime, but high speed factorisation would destroy current encryption methods and that's why the NSA is such a big employer of number theory mathematicians. If one of them cracks it there'll be a huge effect on our society as all internet and electronic banking systems use prime numbers for security.
Noone is trying to list every single prime, but high speed factorisation would destroy current encryption methods and that's why the NSA is such a big employer of number theory mathematicians. If one of them cracks it there'll be a huge effect on our society as all internet and electronic banking systems use prime numbers for security.
No alpha you dont just check +2 -2 the prime... You check every number in the range that a prime has to hit. The thing is you dont check it completely you just check for like 3-20 or something because you will get most of the non primes within that range. What your left with will probably be prime. Soooo like once you get into the hundreds youd have a prime every 10+ or so numbers depending on how high into the hundreds you are. So if you check like 20 numbers in the hundreds and find all the ones that arnt prime you will pretty much know what numbers are prime or could be prime in your set of numbers.
So basicaly you just take the knowledge of how often a prime should hit in that area and use deductive reasoning. Its far better to figure out to a degree all the non primes in an area of large numbers then to just pick a number and try to see if it is prime by itself. If you run into a number that is xyz away from another possible prime and that xyz happens to be the most it could be away from another prime then its pretty much a prime.
So basicaly you just take the knowledge of how often a prime should hit in that area and use deductive reasoning. Its far better to figure out to a degree all the non primes in an area of large numbers then to just pick a number and try to see if it is prime by itself. If you run into a number that is xyz away from another possible prime and that xyz happens to be the most it could be away from another prime then its pretty much a prime.
You are still doing more work than required. Suppose I give you the range 1,000,000 to 1,000,1000. How would you find the primes in that?
Your method seems to be "Why waste time seeing if p is prime when you could just check the numbers p-10, p-9, ...., p+9, p+10 and if they are all non-prime then p is prime". Am I wrong in that assessment? Because that method requires you to check if 20 numbers are prime to see if p is prime. Further more, the distribution of the primes is currently only understood statistically, you can't say "Well when p is about 1000 there's only 1 prime in 20, so there's definitely a prime between p-10 and p+10". For instance, between 20 and 30 there's 2 primes, 23 and 29. Between 40 and 50 there's 3, 41, 43 and 47. Your logic would fail because if you found 41 and 43 you'd say "There can't be more than 2 in 10 so move onto numbers larger than 50".
The pi function can give us an idea of roughly how many primes are in a given interval, but it is not exact.
If I give you 582850385283, how would you check if it's prime? Your method seems to be to consider 580000000000 through to 590000000000, sampling some of them and saying something like "I've checked 1% of the possible values and found 1 in 1000 are prime, so it's unlikely your number of prime". Rather than factorising the number I give you your method factorises (or tries to)other numbers then guesses (using the pi function asymptotic expression someone else has provided you) as to the likelihood the given number is prime. Why not just check the number itself?
Yes, in an ideal world you'd just set a computer running the number sieve so you end up with a list of numbers which aren't prime and thus can see if a given number is on the list but it's very slow and VERY memory intensive. The size of the largest prime is into the millions of digits. To construct a FULL list of all primes smaller than it would be too slow. Which is quicker, factorise p of order 1,000,000,000,000 or work out all primes (or non-primes) less than 1,000,000,000,000?
Your method seems to be "Why waste time seeing if p is prime when you could just check the numbers p-10, p-9, ...., p+9, p+10 and if they are all non-prime then p is prime". Am I wrong in that assessment? Because that method requires you to check if 20 numbers are prime to see if p is prime. Further more, the distribution of the primes is currently only understood statistically, you can't say "Well when p is about 1000 there's only 1 prime in 20, so there's definitely a prime between p-10 and p+10". For instance, between 20 and 30 there's 2 primes, 23 and 29. Between 40 and 50 there's 3, 41, 43 and 47. Your logic would fail because if you found 41 and 43 you'd say "There can't be more than 2 in 10 so move onto numbers larger than 50".
The pi function can give us an idea of roughly how many primes are in a given interval, but it is not exact.
If I give you 582850385283, how would you check if it's prime? Your method seems to be to consider 580000000000 through to 590000000000, sampling some of them and saying something like "I've checked 1% of the possible values and found 1 in 1000 are prime, so it's unlikely your number of prime". Rather than factorising the number I give you your method factorises (or tries to)other numbers then guesses (using the pi function asymptotic expression someone else has provided you) as to the likelihood the given number is prime. Why not just check the number itself?
Yes, in an ideal world you'd just set a computer running the number sieve so you end up with a list of numbers which aren't prime and thus can see if a given number is on the list but it's very slow and VERY memory intensive. The size of the largest prime is into the millions of digits. To construct a FULL list of all primes smaller than it would be too slow. Which is quicker, factorise p of order 1,000,000,000,000 or work out all primes (or non-primes) less than 1,000,000,000,000?
Because checking a number that large to see if its prime takes alot of trys... Where as checking to see if the numbers around it are prime only takes a few. And once you know the numbers in that range that are not prime you will have a very good lead if not for sure knowledge on the ones that are prime.
roughly is good enoth if you give enoth room for error.
so like with 582850385283 first you would find out what the max difference between primes is for that number range. Then you would check about that many numbers up and below it to see if they are not prime. You would already rule out anything ending in 5 so thats about 1/5th of the numbers. Then you would rule out for anything divided by 3 and thats about 1/3rd of the numbers. After doing this with 7,9,11 you wont have many numbers left that are non prime... Its just a faster way of finding a prime. I guess if you can come up with a formula that gives you the primes your looking for in that range go for it...
roughly is good enoth if you give enoth room for error.
so like with 582850385283 first you would find out what the max difference between primes is for that number range. Then you would check about that many numbers up and below it to see if they are not prime. You would already rule out anything ending in 5 so thats about 1/5th of the numbers. Then you would rule out for anything divided by 3 and thats about 1/3rd of the numbers. After doing this with 7,9,11 you wont have many numbers left that are non prime... Its just a faster way of finding a prime. I guess if you can come up with a formula that gives you the primes your looking for in that range go for it...
That's your solution???
Find all the non-primes and what's left are primes????
Find all the non-primes and what's left are primes????
How do you find a needle in a haystack?
Magpies' solution; remove all the hay.
Magpies' solution; remove all the hay.
QUOTE (magpies+Jun 23 2009, 12:39 PM)
Because checking a number that large to see if its prime takes alot of trys... Where as checking to see if the numbers around it are prime only takes a few. And once you know the numbers in that range that are not prime you will have a very good lead if not for sure knowledge on the ones that are prime.
No, that isn't easy. The numbers around p are of the same magnitude as p so working out if they are prime is just as much effort as working out if p itself is prime. And besides, knowing if they are doesn't tell you if p is prime or not.
No, that isn't easy. The numbers around p are of the same magnitude as p so working out if they are prime is just as much effort as working out if p itself is prime. And besides, knowing if they are doesn't tell you if p is prime or not.
QUOTE (magpies+Jun 23 2009, 12:39 PM)
roughly is good enoth if you give enoth room for error.
No, because it either is or it isn't prime, there's no middle ground.
QUOTE (magpies+Jun 23 2009, 12:39 PM)
so like with 582850385283 first you would find out what the max difference between primes is for that number range.
Which you can only do roughly, using approximations to the pi function, as to know the true max difference you'd need to work out the primes themselves, which would result in you factorising (or trying to) the number anyway.
QUOTE (magpies+Jun 23 2009, 12:39 PM)
Then you would check about that many numbers up and below it to see if they are not prime. .
You're claiming it's quicker to try to factorise a load of numbers above and below p rather than just p itself?!
Suppose I asked you if 101 were prime. Would you try to factorise 95, 96, 97, 98, 99, 100, 102, 103, 104, 105, 106 and 107 or just look directly at 101? How would you work out if 97 is prime? Check 85, 86, 87, 88, 89, 90, etc ? By your method each number requires you to look at 2, 5, 10, 100 more, which in turn each need to have other numbers looked at. It's more effort than just considering one number.
Suppose I asked you if 101 were prime. Would you try to factorise 95, 96, 97, 98, 99, 100, 102, 103, 104, 105, 106 and 107 or just look directly at 101? How would you work out if 97 is prime? Check 85, 86, 87, 88, 89, 90, etc ? By your method each number requires you to look at 2, 5, 10, 100 more, which in turn each need to have other numbers looked at. It's more effort than just considering one number.
QUOTE (magpies+Jun 23 2009, 12:39 PM)
You would already rule out anything ending in 5 so thats about 1/5th of the numbers. Then you would rule out for anything divided by 3 and thats about 1/3rd of the numbers. After doing this with 7,9,11 you wont have many numbers left that are non prime... Its just a faster way of finding a prime. I guess if you can come up with a formula that gives you the primes your looking for in that range go for it...
That's the number sieve I mentioned. And it's only good for 'small' numbers, like less than 100,000,000. That might sound a lot but the primes used in internet encryption run into the thousands of digits. It'd take more time and computer memory to construct a full list via the number sieve than using number theory methods to attack a number directly. Modular arithmetic is very powerful for this and it's a surprisingly straight forward area of maths for beginners (at least the basics of it). Look it up and then read the Fermat's Little Theorem link I provided. I think you drastically underestimate the size of primes involved in even purchases on Amazon, never mind bank transactions or number theory problems. The number sieve is 'brute force', you just do something very simple a lot. Modern methods involve doing cleverer things less. If you read the literature on code breaking and the RSA method you'll see how pitiful brute force techniques are. In 5 minutes my netbook can encrypt something which would take all the computers on Earth longer than the age of the universe to decrypt using your method. As it stands, it still takes other methods millions of years.
Indeed, in pursuing the question, inspired by Raphie Frank, of the series b_n = (b_{n-1})^2 - 2 ever has additional primes beyond b(1) = 3, b(2) = 7, b(3) = 47, b(4) = 2207, ... I needed some powerful methods to prove the numbers prime or composite.
b(13) = a(8192) = 106352799892788493110153690447343447305470461839801749696888904326793822501807523858343368817374906071055883020948513173454934275225964193652567805803093812427396216375497396011426701253537040886005058364455749508379332460068863273209362959211349695940992965287501020465878192236379910996201246410952503288582362187697323696152715258347507554225929317934354812864403928775594189364372534345190756371310821050130456496752730896560557090600635970693008450571523015564151725610119684508144165403330461173232751131580337443954064658145831159957490227960266786882241002797161000132349989681771373659042440825339587753496034215354174180882342606891519666762174814589937832916347605938886393346759579533095469236801706417967993461442257672990927199494961969540216293178443558375799261101214910353496376696966116034407448019538663751360223550121654027258862014313329045408270050541733443965519859471647956029416780580658494748034461836394695473721726251355786224135077600672018223272986827418873344211259914685891948265104665410891785898850985208482867129812960455716871960916151438290908981447348308505752069195875345801164338971873752388784257588390965689486787558399481835958463278218442281288972079544765108396832760769088884560324747007796054306029913968807790745720370504594274537869265965934894432425875393151213643849488026856220837544470554233075366408557809059873632701041552713034095222195724966458636832609260553157412414706490526236978187501358385792586601605835876189691641049462810938225466524678771277916462642973015490018279647696101595540712249410013175032489879191921472731396498012877730568542083001326763588214716437813175362270505999306955046622201907495073417434834966899533608716262480958153474047
b(13) is not prime, but that's not going to help you find its factors.
So in algorithms or number theory, you cannot let your prejudices based on small numbers influence your reasoning about large numbers.
b(13) = a(8192) = 106352799892788493110153690447343447305470461839801749696888904326793822501807523858343368817374906071055883020948513173454934275225964193652567805803093812427396216375497396011426701253537040886005058364455749508379332460068863273209362959211349695940992965287501020465878192236379910996201246410952503288582362187697323696152715258347507554225929317934354812864403928775594189364372534345190756371310821050130456496752730896560557090600635970693008450571523015564151725610119684508144165403330461173232751131580337443954064658145831159957490227960266786882241002797161000132349989681771373659042440825339587753496034215354174180882342606891519666762174814589937832916347605938886393346759579533095469236801706417967993461442257672990927199494961969540216293178443558375799261101214910353496376696966116034407448019538663751360223550121654027258862014313329045408270050541733443965519859471647956029416780580658494748034461836394695473721726251355786224135077600672018223272986827418873344211259914685891948265104665410891785898850985208482867129812960455716871960916151438290908981447348308505752069195875345801164338971873752388784257588390965689486787558399481835958463278218442281288972079544765108396832760769088884560324747007796054306029913968807790745720370504594274537869265965934894432425875393151213643849488026856220837544470554233075366408557809059873632701041552713034095222195724966458636832609260553157412414706490526236978187501358385792586601605835876189691641049462810938225466524678771277916462642973015490018279647696101595540712249410013175032489879191921472731396498012877730568542083001326763588214716437813175362270505999306955046622201907495073417434834966899533608716262480958153474047
b(13) is not prime, but that's not going to help you find its factors.
So in algorithms or number theory, you cannot let your prejudices based on small numbers influence your reasoning about large numbers.
QUOTE (magpies+Jun 23 2009, 04:54 AM)
Primes wont be solved solved even in 1000 billion years.
Perhaps we will let you post then, but you seem intemperate to say the least.
Wow, Rpenner. In spite of recent adversarial tendencies (which I do not desire), I thank you for following through on this. I have been quite curious regarding b(13).
OEIS, incidentally, is due for an update regarding the following sequence:
A118841
Numbers n such that Ceiling[GoldenRatio^n] is prime.
http://www.research.att.com/~njas/sequences/A118841
Best,
Raphie
Related thread / post by RPenner
N Such That Ceiling[goldenratio^n] Is Prime, Can anyone explain this?
http://www.physforum.com/index.php?showtop...ndpost&p=407672
OEIS, incidentally, is due for an update regarding the following sequence:
A118841
Numbers n such that Ceiling[GoldenRatio^n] is prime.
http://www.research.att.com/~njas/sequences/A118841
Best,
Raphie
Related thread / post by RPenner
N Such That Ceiling[goldenratio^n] Is Prime, Can anyone explain this?
http://www.physforum.com/index.php?showtop...ndpost&p=407672
It's too boring a update to report.
QUOTE (rpenner+Jun 24 2009, 06:17 AM)
It's too boring a update to report.
With all due respect, Dr. Penner, boring is in in the eye of the beholder.
Anyone who would KNOWINGLY let less than accurate information be regarded as "scientific truth" upon OEIS or elsewhere is complicit in a bastardization of "truth"
But I am just a layman, of course. What do I know?
An immediate "out" for you, Dr. Penner... humility. I recognize that you do not believe yourself capable of meaningful discovery. That you are incorrect in this belief (or not) is either "proof" of my stupidity or "proof" of your (self-unacknowledged) intelligence.
Best,
Raphie
With all due respect, Dr. Penner, boring is in in the eye of the beholder.
Anyone who would KNOWINGLY let less than accurate information be regarded as "scientific truth" upon OEIS or elsewhere is complicit in a bastardization of "truth"
But I am just a layman, of course. What do I know?
An immediate "out" for you, Dr. Penner... humility. I recognize that you do not believe yourself capable of meaningful discovery. That you are incorrect in this belief (or not) is either "proof" of my stupidity or "proof" of your (self-unacknowledged) intelligence.
Best,
Raphie
I was not, of course, being overly serious, RPenner, and thank you again for publishing the results regarding b(13).
Best,
Raphie
Best,
Raphie
PhysOrg scientific forums are totally dedicated to science, physics, and technology. Besides topical forums such as nanotechnology, quantum physics, silicon and III-V technology, applied physics, materials, space and others, you can also join our news and publications discussions. We also provide an off-topic forum category. If you need specific help on a scientific problem or have a question related to physics or technology, visit the PhysOrg Forums. Here you’ll find experts from various fields online every day.
To quit out of "lo-fi" mode and return to the regular forums, please click here.