Results 1 to 24 of 24

Thread: Record probable prime found!

  1. #1
    Free-DC's Prime Search
    Join Date
    Apr 2004
    Posts
    2,518

    Record probable prime found!

    Quote Originally Posted by philmoore
    Congratulations to Ben Maloney (paleseptember) who discovered the probable prime [tex]2^{1518191}+75353[/tex]. At 457,022 decimal digits, it should soon appear as the new probable prime record at the website of Henri and Renaud Lifchitz, PRP Records, Probable Primes Top 10000. We have performed strong probable prime tests on this number to all 20 prime bases from 2 to 71. The probability that a random number of this size that passes even one strong probable prime test is composite is less than [tex]10^{-728}[/tex]. This eliminates the first of the five sequences, and should speed up our PRP testing by over 20% as well as our sieving by around 10%. I have already uploaded new work files and will get a new sieve file up soon as well. Thanks to everyone who contributed to this effort!

    And now for the embarrassing part - this prp actually showed up in early November, but was not noticed by either of us! In fact, PRP testing is currently approaching 630,000 digits, a good bit beyond this record. I visually scanned all of the results files when they came in, but obviously, out of the more than 300 results in this file, I overlooked the important one! Moral: computers make fewer mistakes than humans, so always search the file for the string "probable". Ben says he did search, but specified the wrong string. Unfortunately, it means that 20% of our PRP testing the past two months was unnecessary, but in the long run, that is probably a drop in the bucket compared to what comes next. All I can say is that it will not happen again!

    We are close to finishing PRP testing up to n=2^21, about 2.1 million. In the range from 2^21 to 2^22, I calculate that we should expect about 0.667 new primes. Let's go find another one!
    http://www.mersenneforum.org/showthread.php?t=11296

  2. #2
    Administrator Bok's Avatar
    Join Date
    Oct 2003
    Location
    Wake Forest, North Carolina, United States
    Posts
    22,233
    Blog Entries
    13
    nice.

    Congrats PaleSeptember !!

  3. #3
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290
    <Does the (probable) Prime Happy Dance>

    I've been bouncing off the walls with excitement these last two days whilst Phil ran some of the confirmation tests. In the linky'd thread, he calculates it'd take ~500 million years to verify it as an actual prime. I think I'll be happy with a probable in the meantime!

    Onwards to another one! Woo!

  4. #4
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619

  5. #5
    Dungeon Master alpha's Avatar
    Join Date
    Mar 2002
    Location
    Norfolk, UK
    Posts
    1,700
    Wow, congrats paleseptember, that's great news!

    I'm surprised it would take so long to do a full primality test. It only took a single core of my C2D 20 minutes to confirm a ~45,000 digit prime using PFGW. I guess the time taken to perform these tests must increase exponentially with the length of the number.

  6. #6
    Free-DC Semi-retire gopher_yarrowzoo's Avatar
    Join Date
    Mar 2002
    Location
    Santa Ana, CA
    Posts
    3,982
    nice one paleseptember, now can someone show me the full number
    Semi-retired from Free-DC...
    I have some time to help.....
    I need a new laptop,but who needs a laptop when you have a phone...


  7. #7
    Congrats, that is great news. Also very good timing as I will use that information in my talk on prime numbers in a couple of weeks. It will be especially good to use that as a concrete example of how deterministic primality testing in the general case takes a LONG time (ie: 500 million years) compared to specialized cases like Mersenne Primes which can be 28x larger (ie: 12.9 million digits) and only take a week or two to verify.

    Jeff.

  8. #8
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290
    Quote Originally Posted by Digital Parasite View Post
    Congrats, that is great news. Also very good timing as I will use that information in my talk on prime numbers in a couple of weeks. It will be especially good to use that as a concrete example of how deterministic primality testing in the general case takes a LONG time (ie: 500 million years) compared to specialized cases like Mersenne Primes which can be 28x larger (ie: 12.9 million digits) and only take a week or two to verify.

    Jeff.
    Glad that I, the project, and Phil (the project admin) could be of service for your talk!

    Do post about how your talk went And remember that you'll have all of Free-DC (in spirit) sitting up the back pulling silly faces to try to distract you from your notes!

  9. #9
    Free-DC Semi-retire gopher_yarrowzoo's Avatar
    Join Date
    Mar 2002
    Location
    Santa Ana, CA
    Posts
    3,982
    paleseptember - exactly defiantly pulling the faces, or just mastering the one "look"... or just going probability ratio 1: 2^n-1 and falling... aka from Hitchhikers....
    Semi-retired from Free-DC...
    I have some time to help.....
    I need a new laptop,but who needs a laptop when you have a phone...


  10. #10
    Old Timer jasong's Avatar
    Join Date
    Oct 2004
    Location
    Arkansas(US)
    Posts
    1,778
    Quote Originally Posted by paleseptember View Post
    <Does the (probable) Prime Happy Dance>

    I've been bouncing off the walls with excitement these last two days whilst Phil ran some of the confirmation tests. In the linky'd thread, he calculates it'd take ~500 million years to verify it as an actual prime. I think I'll be happy with a probable in the meantime!

    Onwards to another one! Woo!
    Assuming the 500 million years refers to testing on one core of a modern computer, and assuming Moore's Law isn't broken, they should be able to actually test for primality sometime around the year 2065 or so.

    Be sure to contact me on the psychic Internet link to Mars, so I can tell my female clone(shouldn't take many changes to make a female version of me) the good news.

    And, yes, I'm both bored and very loony. lol

  11. #11
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290

    (Another) record probable prime

    I don't really wish (oh yes I do!) to cheer my own achievements (well, my computer's acheivements), but!

    http://www.mersenneforum.org/showthread.php?t=11425

    In summary, with a stupid amount of luck, we've eliminated the second of five sequences for the Dual Sierpinski Conjecture Huge huge thanks to the sievers, and especially engracio who has been flying through the sieving!

    Quote Originally Posted by Phil Moore
    (paraphrased) 2^2249255+28433 is a probable prime, and at 677,094 digits, would take about 3 billion years at current technology to verify prime.


    <cue the happy dance>


    Edit: Digital Parasite: Another data point for your presentation about deterministic primality testing? <grins>

  12. #12
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619

  13. #13
    Doh too late, the presentation was this past Friday. Wow that was quite a jump, congrats again.

    I think the talk went very well, people asked lots of questions and seemed interested. They were very suprised about the 400k digit one you found that would take 500 million years to verify, this would have floored them even more.

  14. #14
    Unholy Undead Death's Avatar
    Join Date
    Sep 2003
    Location
    Kyiv, Ukraine
    Posts
    907
    Blog Entries
    1
    why does it takes so long to chack primality?

    just because it's not in form k*n^2+-1, am I right?
    that's +28433 make such a difference?
    wbr, Me. Dead J. Dona \


  15. #15
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290
    Death: I'm probably not the person to be answering those questions, but I'll give it a shot. There are shortcuts for sierpinski and riesel numbers (those forms that you suggested). Unfortunately, there doesn't seem to be such shortcuts for other forms.

    There are some more details at the coordinating forum: http://www.mersenneforum.org/forumdisplay.php?f=86

    Phil Moore wrote a good introduction to the project. The Integers paper (linked in the SoB forum here at Free-DC, the main SoB site, and the mersenneforum linked above) had some more technical details if you're interested.

  16. #16
    Unholy Undead Death's Avatar
    Join Date
    Sep 2003
    Location
    Kyiv, Ukraine
    Posts
    907
    Blog Entries
    1
    afaik mercenne numers are so popular to primality check because there IS a simple and fast way to primality check. I read this in mercenne.org.
    so there's NO fast way to check +123 numbers.
    wbr, Me. Dead J. Dona \


  17. #17
    Quote Originally Posted by Death View Post
    afaik mercenne numers are so popular to primality check because there IS a simple and fast way to primality check. I read this in mercenne.org.
    so there's NO fast way to check +123 numbers.
    That is right, there are specialized primality tests for some numbers of special form like Mersenne numbers. That is why Mersenne numbers and Proth primes dominate the top largest known primes list: http://primes.utm.edu/largest.html

    The Lucas-Lehmer test (used for Mersenne numbers) is the fastest deterministic test on the planet and so not surprisingly it was the method used to find the top 8 primes listed. If you don't have a number of a special form, then the fastest test you have is ECPP (Elliptic Curve Primality Proof). The largest number ever proven using ECPP is 20562 digits long (http://primes.utm.edu/top20/page.php?id=27) and that was a significant effort using many machines. So you can see the limitation of what is practical with current systems.

    Just 60 years ago, the largest known prime number was only 44 digits long so we have come a long way since the start of the computing era.

  18. #18
    paleseptember, I hear it is mighty hot down under these days. Hopefully all your computers aren't starting to melt...

  19. #19
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290
    DP: It's horrendous down in Melbourne and Adelaide. They just set a record for consecutive days above 40C (104F). It topped 45C yesterday (113F). It's not quite so bad up here in Wollongong, as I'm five minutes from the ocean on the east, and an escarpment on the west. The heat is pretty much pushed over the top of the city and settled on the water when we have strong Westerlys. It's still mid- to high-30s during the day though.

    However, we're all waiting for the horror situation to develop:

    Quote Originally Posted by AAP Reuters
    In South Australia , some homes and businesses suffered power cuts as the National Electricity Market Management Company (NEMMCO) strived to maintain services in the face of record demand.

    It was the second day in a row that power cuts were required, after supplies to an estimated 95,000 homes in more than 40 suburbs were turned off for short periods on Thursday.

    NEMMCO also directed that power be cut to 42,000 Melbourne homes on Friday.
    Everything is so very very dry. There are already fires starting on the outskirts of Melbourne. Five houses were lost yesterday. One tossed cigarette or bottle, this intense dry heat, and a strong wind, and we're looking at serious bushfires. Again.

    Gotta love Orrrstraya



    However, my flat in on the ground floor of a nice old brick building, facing south-ish, so it stays a fair bit cooler. And my office computer, well, yeah. I'll have to get a close eye on it. I've moved into the library a few times this last week already!

  20. #20
    Quote Originally Posted by paleseptember View Post
    DP: It's horrendous down in Melbourne and Adelaide. They just set a record for consecutive days above 40C (104F). It topped 45C yesterday (113F). It's not quite so bad up here in Wollongong, as I'm five minutes from the ocean on the east, and an escarpment on the west.
    Yikes. I have never been to Wollongong, the furthest south I have been in Sydney and I spent a few weeks in the Brisbane and Frasier Island area in 2000. If it get too hot for you, come and visit here, we are having a heat wave here too, supposed to get up to 0C tomorrow (right now -31C with the wind chill).

  21. #21
    Sheesh, he did it a again! This time he found the first million+ digit probable prime:
    http://www.mersenneforum.org/showthread.php?t=12376

    To prove that this number is actually prime would take around 125 billion years if we could gear up ECPP on a single processor.
    That is a spicy meat-a-ball!

  22. #22
    Senior Member paleseptember's Avatar
    Join Date
    Nov 2005
    Location
    Wollongong, Australia
    Posts
    290
    It's a statistical anomaly, I swear! There is a dedicated group on the project: Geoff, Kent, Engracio, Jeff, Serge, Geoff, Phil, and Dmitry, all of whom are slowly chipping away at the moment. I just got lucky. Three times. Ummmm....

    And George Woltman for Prime95 and Geoff Reynolds for sr2sieve! Their code is l33t!

  23. #23
    Quote Originally Posted by paleseptember View Post
    It's a statistical anomaly, I swear! I just got lucky. Three times. Ummmm....
    Now that you have done it 3 times, we are going to be disappointed if you don't get all 5...

    Jeff.

  24. #24
    DinkaTronic Shish's Avatar
    Join Date
    May 2005
    Location
    Gateshead UK
    Posts
    882
    I think all 5 would entitle PS to the Freedom of Free_DC and special status.. But I think the group should devote themselves to actually proving the primes . That should keep them occupied until hell freezes over and so out of any mischief
    Like an ol` 8086, slow but serviceable.
    One advantage of old age...nobody can tell you how much cake you can eat


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •