Slashdot Mirror

← Back to Stories (view on slashdot.org)

SB Project Announces 4th-Largest Known Prime

Posted by timothy on from the keep-counting dept.

alien88 writes "The Seventeen or Bust project announced today that they have discovered the fourth largest prime on record. The prime is 1,521,561 digits long and is their sixth discovery since the start of the project. They now have 11 multipliers left to prove that k = 78,557 is the smallest Sierpinski number. Randy Sundquist of Team ExtremeDC's computer discovered the number on December 6th."

39 comments

  1. you just knew it by kurosawdust · · Score: 4, Funny

    In a related story, the BCS rankings for prime numbers were also released, with "2" garnering the top spot. Consequently, a lot of journalists got pissed off.

    1. Re:you just knew it by Anonymous Coward · · Score: 0

      HAHA

      If this wasn't Slashdot, and a forum where people actually knew a thing or two about NCAA Football, this would have been +5 Funny.

    2. Re:you just knew it by KDan · · Score: 2, Insightful

      Let's patent it right now !!!

      Daniel

      --
      Carpe Diem
  2. Re:How do they know it's the 4th largest prime? by Anonymous Coward · · Score: 1, Funny

    because they counted them all, duh.

  3. Re:How do they know it's the 4th largest prime? by l0tu53at3r · · Score: 0

    Please, next time you ask a question regarding the wording of a topic, include the entire quote with context.

    read: "on record"

    --
    ---Excuse the bad English, I'm American---
  4. what's a number? by zwanglos · · Score: 0, Flamebait

    Wow, this is going to completely blow away the four Americans who can still add.

    -in search of a ship, a bone, and a way the hell outta here....

    1. Re:what's a number? by l0tu53at3r · · Score: 0

      Yeah, my American Calculus can't hold up to this sort of dividing. :-)

      --
      ---Excuse the bad English, I'm American---
    2. Re:what's a number? by moncyb · · Score: 1

      Dude! Didn't you hear? Americans don't add anymore. The Americans passed a law making addtion illegal. They are directed to used exclusive or instead. It's faster! Here in Soviet Russia, exclusive or adds you!

  5. Inquiring minds want to know. by Eevee · · Score: 2, Interesting

    Does k have to be odd?

    The page for Sierpinski numbers uses both k and (2k - 1). But the page on Riesel numbers seems to say k needs to be odd.

    What's so neat about Sierpinski numbers?

    Is there a real-life use for numbers that are excessively composite?

    And, finally....

    What's a Sierpinski number of the first kind?

    1. Re:Inquiring minds want to know. by alien88 · · Score: 4, Informative

      Chris Caldwell's page pretty much answers your questions concerning Sierpinski numbers and Risel numbers.

      http://primes.utm.edu/glossary/page.php?sort=Sie rp inskiNumber

      http://primes.utm.edu/glossary/page.php?sort=Rie se lNumber

    2. Re:Inquiring minds want to know. by ph43thon · · Score: 1

      Well.. say k not odd. Then k = 2m for some m.
      Then we'd have:

      k(2^n) + 1 = (2m)(2^n) + 1

      which turns into m(2^(n+1)) + 1

      So, then you ask.. what is m ?

      Either you get, (2^(n+r)) if k simply equaled 2^r .. which then gives rise to something that I'm too hungover to recall (probably says that it will eventually spit out a prime ie (2^n) + 1 is prime for some n..

      OR

      you'd eventually terminate at some odd number. The main point is: for all n = 2k , n = (2^r)m for some r > 0 and some odd m > 0

      p

  6. Proof by Veramocor · · Score: 1

    It seems as if this test can only prove that a number is not a Sierpinsky number by showing it forms a prime number at some 'n'. But since n has no bounds you can never really prove that a number is a sierpinsky number.

    --
    Veramocor
    1. Re:Proof by alien88 · · Score: 4, Informative

      It is believed that 78557 is the smallest Sierpinski number, and that is what we are trying to prove. There were 17 values, when this project started, that a prime had not been found in. We are working on finding a prime in these values (11 remaining) which will then prove that 78557 is, indeed, the smallest Sierpinski number. See Chris Caldwell's page for more information.

    2. Re:Proof by You're+All+Wrong · · Score: 4, Informative

      You can construct an infinite number of provable sierpinski numbers through finding what are called "covering sets". These are sets of factors that repeat in the sequence k*2^n+1, with fixed k, and variable n.
      e.g. as long as k is not divisible by 3, then half of the values k*2^n+1 will be divisible by 3. For some k it will be the even n's, for other k it will be the odd n's. Either way, you've already covered half the possibilities with a known factor. Fill in 1/4 of the values by ensuring that 5 divides half of the ones not divisible by 3, hey presto - only 1/4 now remain. 17 can remove 1/8, leaving 1/8. 65537 can remove 1/16, leaving 1/16. Between them, 241, 97 and 673 can remove 1/16 (as they can each remove 1/48). That's it - there's your covering set {3,5,17,65537,241,97,673}.
      Finding which k values actually use this covering set is an exercise in using the Chinese Remainder Theorem.
      (note - may be errors in the above, I did it off the top of my head, but looks right.)

      If you can't find a covering set, and for the remaining 11 numbers that looks most likely, then you're right, you can't know for sure that there is no prime.

      YAW.

      --
      Your head of state is a corrupt weasel, I hope you're happy.
    3. Re:Proof by JohnPM · · Score: 1

      ...may be errors in the above...

      If you can't find a covering set, and for the remaining 11 numbers that looks most likely, then you're right, you can't know for sure that there is no prime.

      There may be errors in the below too! You're assuming that there is no proof strategy alternative to covering sets. Maybe no one has thought of an alternative because covering sets have thus far shown the most promise?

      --
      Karma police, I've given all I can, it's not enough, I've given all I can, but we're still on the payroll.
    4. Re:Proof by You're+All+Wrong · · Score: 1

      Maybe, maybe not, depending on whether you admit the concept of infinite covering sets. Any other proof strategy of which you speak could quite probably be reworked just an infinite covering set. (As if it were constructive, for example, it would lead /immediately/ to an (infinite number of) infinite covering set(s).)

      Not everyone espouses infinite covering sets as a possibility, so if you don't you're certainly not on your own.

      My personal view is that pretty much everything to do with prime densities that is based on the existance or non-existance of factors follows the heuristics (such as k-tuplet densities and the "C_n" figures for various cyclotomic types, but _not_ wieferich/SSW primes), and the heuristics point to Seventeen-or-Bust running out of numbers to test by the time they've reached n=10^12 or similar. Which makes me definitely an infinite covering set sceptic.

      So yes, my bias was coming through.

      YAW.

      --
      Your head of state is a corrupt weasel, I hope you're happy.
    5. Re:Proof by ngoy · · Score: 1

      Ok, I am "American", (well, Taiwanese, Russian, and Jewish), and finished Calculus A/B in high school. I have not had to do much advanced math at all, but cannot for the life of me figure out what the use of finding the smallest Sierpinski number is. Real or imaginary. Can I come up with some arbitrary equation and then put my name on it so it sits in the annals of math history for all time? Or does the equation have to have something = 1 somewhere?

      Not trying to be sarcastic, but I have seen tons of "math theorems" and I guess I am not geeky enough to understand the point. It is not like using integration to infinity to find the area underneath a curve. I did glance through Chris' website but the only thing I can figure out is that maybe it helps with encryption? How?

      --
      --ngoy
    6. Re:Proof by sasami · · Score: 2, Insightful

      Not trying to be sarcastic, but I have seen tons of "math theorems" and I guess I am not geeky enough to understand the point.

      There's no need to have a point because the assumption is that someone will eventually find a use for it. In mathematics, physics, and all sorts of other disciplines, you don't look at your discovery and say "This would be great for X!" You publish it, forget about it, and then someone else years later has a problem to solve and does a literature search.

      In the mid-1800s some poor sod went and developed a whole branch of mathematics called tensor calculus. It was an absolute mess and no one used it for anything.

      Until fifty years later, Einstein is having trouble formalizing relativity and talks to his mathematician friend, who replies, "Oh, you know, I think I heard of something once..."

      ---
      Dum de dum.

      --
      Freedom is not the license to do what we like, it is the power to do what we ought.
    7. Re:Proof by alien88 · · Score: 1

      To be honest, there really isnt much of a point besides saying "Hey, we proved it."

      The project idea actually came out of a book of a bunch of math theorms that havent been proved yet..

    8. Re:Proof by exp(pi*sqrt(163)) · · Score: 1
      But since n has no bounds you can never really prove that a number is a sierpinsky number.
      If that were a valid form of argument then you'd never really know if 2n>n for all integers n>0 because n is unbounded. The fact that a value in a proposition is unbounded doesn't prevent something being proved for all such values.
      --
      Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
    9. Re:Proof by Anonymous Coward · · Score: 0

      Now, that's not exactly true. Tensor calculus was used for stresses (tensions and compressions) in solids before relativity. Tension. Tensor.

  7. www.seventeenorbust.com by Chuq · · Score: 4, Funny

    Does anyone else think www.seventeenorbust.com sounds like a porn site?

    --
    - Chuq
    1. Re:www.seventeenorbust.com by moncyb · · Score: 4, Funny

      It is! It is! If you store their secret prime number in your user account, you can view pictures of barely illegal naked teens! ;-9 The bad news is it takes 7 days to verify. ;-(

  8. This didn't make the main page??? by Anonymous Coward · · Score: 5, Interesting

    Wow! I'm surprised ... coming on the heels of GIMPS 6+ million digit prime. At 1.5+ million digits, it's not only the world's 4th largest known prime, but is the FIRST known prime with more than 1 million digits that's not a Mersenne prime (not of the form 2^p-1)! This is important because the primality of this form, k*2^n+1, (while still allowing some optimizations) is much harder to check than the Mersennes and their close cousins, the Generalized Fermats, who together occupy the other 7 positions in the top 8 largest known primes!

    Greg

  9. does anybody know... by Dreadlord · · Score: 2, Funny

    ... how many prime numbers left and we discover the secrets of life?

    --
    The IT section color scheme sucks.
    1. Re:does anybody know... by Anonymous Coward · · Score: 0

      42

  10. Largest Prime by Bloodmoon1 · · Score: 4, Informative

    And, for those curious, the largest prime curently known is the 40th Mersenne Prime 2 to the 20,996,011 -1, which is 6,320,430 decimal digits in length. If you're wondering what that looks like, and don't mind downloading 6.3 MB, wonder no more.

    --

    Request: ECM unit, 1000 km fullerene cable, 1 tactical nuclear weapon. Reason: Birthday party for foreign dignitary.
    1. Re:Largest Prime by Void_of_light · · Score: 1

      cool use the down arrow key to scroll imagine a black background and a green font and they have discovered the matrix.

  11. Primes and our universe by BallPeenHammer · · Score: 5, Interesting
    From http://www.prothsearch.net/sierp.html

    "The Sierpinski Problem: Definition and Status In 1960 Waclaw Sierpinski (1882-1969) proved the following interesting result.

    Theorem [S]. There exist infinitely many odd integers k such that k*2n + 1 is composite for every n > 1.

    A multiplier k with this property is called a Sierpinski number. The Sierpinski problem consists in determining the smallest Sierpinski number. In 1962, John Selfridge discovered the Sierpinski number k = 78557, which is now believed to be in fact the smallest such number.

    Conjecture. The integer k = 78557 is the smallest Sierpinski number.

    To prove the conjecture, it suffices to exhibit a prime k*2n + 1 for each k less than 78557. By August 1997, this had been done for all except the following 21 values of k less than 78557. As long as a prime is not found for a listed k, that k might be considered a potential Sierpinski number. However, as the conjecture suggests, in the long run a prime is expected to emerge for each of these k."

    So, what these folks have done is found a prime for another candidate k less than 78557.

    I find the search for primes -- and for more complicated results, like this one, that use primes -- to be fascinating. There is something so pure about this world of mathematics. (As Kronecker is quoted as saying, "God made the integers; all else is the work of Man.") This kind of study says something very deep about the nature of the universe we live in.

    If there are other intelligent beings in the universe, it is fascinating to contemplate that -- no matter what other differences we may have -- they may be finding out these same facts about pure mathematics. It's a language we have in common.

    --
    The Law of Falling Bodies
  12. Poor left out even numbers.... by andy666 · · Score: 2, Interesting

    I've always thought it is unfair that only odd numbers can be prime. Why not define a number to be prime if its only possible divisors are pm 1, pm itelf, OR possibly pm 2. That way we would have a much richer collection of numbers to consider as prime.

    1. Re:Poor left out even numbers.... by Carnildo · · Score: 2, Informative

      I've always thought it is unfair that only odd numbers can be prime.

      2 is both even and prime.

      --
      "They redundantly repeated themselves over and over again incessantly without end ad infinitum" -- ibid.
    2. Re:Poor left out even numbers.... by andy666 · · Score: 1

      Oh but please, we all know that that is only because 2 is so close with 1 & 3, two "giants" of the number world. Politics aside, it shouldn't be considered prime.

    3. Re:Poor left out even numbers.... by Anonymous Coward · · Score: 0

      If it's divisible by 2, it's also divisible by another number. The only number divisible by 1, 2, and itself is 4.

  13. OK, so maybe I'm a savage... by drlake · · Score: 1

    but, why do we bother with the search for ever larger prime numbers? Is there any actual point to knowing that 2^20+million-1 is a prime number 6.3 million digits long? I'm genuinely curious about this. I'm an academic, and some of my colleagues do research that seems completely unconnected from any utility whatsoever, so I am familiar with that practice. I'm just wondering if that's what is going on here, or if there is some deeper utility to this, like maybe helping develop the perfect recipe for chocolate chip cookies?

    1. Re:OK, so maybe I'm a savage... by Anonymous Coward · · Score: 0

      It's not necessarily the search that's the benefit but the algorithms that are designed to facilitate the search.

      As people look for larger and larger primes, the algorithms used to test if a number is prime need to become better and better (and/or you need to throw more computing resources at the problem.) The practical impact of this is that several cryptosystems' security depend on using large prime numbers either as keys directly or to generate keys (RSA anyone?)

      For example, if you use a number that's not prime, the assumptions the RSA algorithm uses may break down (in particular, your private key may not be a unique number, there may be others that can be used to decode the message.)

      In addition, the primality tests are generally fairly computationally intensive and can be used to perform stress-test comparisons of different machines. Not all benchmarks would really push modern machines to really exert themselves to the fullest -- primality testing does, though, since there's so much work that needs to be done, even with good algorithms.

      Finally, there are a lot of theorems in mathematics, physics, etc. with practical impact that depend on properties of primes -- if you're curious, take a look in some advanced physics texts and see how many references to the Riemann Hypothesis you can find. The more information we have about primes, especially where data about them is sparse (i.e. for large primes), the more likely it is that someone will notice some pattern that they then prove and with which progress on the Hypothesis can be made.

  14. Usefulness? by tqft · · Score: 2, Interesting

    Maybe not immediately.

    However read some of the above stuff & links about the type of number.

    Possible practical application:
    In the fields of cyrptography/encryption - it is not beyond the realms of imagination to want to have a number which is known to be factorable, not necessarily having the factors, but very large. 78557*2^<huge number> + 1 would then be very handy. There is also a search on somewhere for more of these numbers.

    Less obvious:
    Symmetries, algebraic topology stuff. While I know almost completely nothing (I don't even know enough to brag about my ignorance), as people dig deeper into the links between calculus and number theory - eg Andrew Wiles and Fermat's Last Theorem proof is based on his proof of the Taniyama's Conjecture, what is slowing evolving is some understanding that will hopefully become more accessible of the links between number theory and calculus. What type of symmetries can 78557*2^<>+1 have and does it tell us anything about the algebraic topology stuff related to its construction which may then feed down into calculus (& even possibly physics).

    What has me interested is why is 78557 the smallest number with this property? Why is it so special? Hopefully there may be answer before I die.

    --
    The Singularity is closer than you think
    Quant
  15. Inquiring minds want to know about the license... by Anonymous Coward · · Score: 0

    Quoting from the signup page:

    License
    This system is Copyright (C) 2002 by Louis Helm and David Norris. The system may only be used in its intended spirit of solving the Sierpinski problem. Any other use whatsoever constitutes unauthorized use and is punsihable under the Digital Millennium Copyright Act.

    (their typo on "punishable", not mine)

    What's up with the DMCA reference? I would have thought a project run by such bright people would be a bit more enlightened...

  16. decimal expansion by suitti · · Score: 1
    A press release and a decimal expansion of the number are coming soon.
    ...the 1,521,561-digit prime...
    53592^5054502+1
    For Unix (and Linux) users, the bc script:
    5359 * (2 ^ 5054502) + 1
    produces the decimal expansion in about 5 minutes on a PIII/800. As bc works, it's resident set size increases, reaching a maximum of about 6.6 MB of RAM. So, a 386 with 8 MB RAM running Linux could easily compute this result in 2 to 3 hours.

    One could publish the number easily enough. A bzip2 compressed verion is about 656,116 bytes. However, just running the calculation in bc seems reasonable at this point, avoiding a slashdot effect. That is, assuming you needed to know, for some reason.

    --
    -- Stephen.