Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Double check - this is prime, yes?

  1. Jul 25, 2007 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Double check -- this is prime, yes?

    I thought I had uncovered some kind of pseudoprime, since I found this number with pfgw and on checking it, found it to be composite. I tested it for pseudoprimality with a battery of tests, though, and it passed all of them -- leading me to think that I was mistaken in the first place and tested some other number by typo. But on the off chance it is a pseudoprime I'd like to know, since it would be the only known Baillie-Pomerance-Selfridge-Wagstaff pseudoprime.

    The 9928-digit number is:
    32986!/(2*(16493!)^2)+1
     
  2. jcsd
  3. Jul 25, 2007 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    After about 4 minutes of thinking very hard, Mathematica confirms that
    32986!/(2*(16493!)^2) + 1
    is prime.

    PS It found no divisors but 1 and itself. Which could be viewed as a confirmation of either the fact that it's prime, or that the PrimeQ[] function first finds the divisors and then checks how many there are :smile:
     
    Last edited: Jul 25, 2007
  4. Jul 25, 2007 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I don't imagine you know what kind of test it used to determine that? I've run a (B)PSW test (a 2-strong plus a (21, -1)-Lucas test in this case) and 10 strong (Rabin-Miller) tests with random bases. The latter has worst-case error of 2^-20.
     
    Last edited: Jul 25, 2007
  5. Jul 25, 2007 #4
    how much math should i have before i attempt to self-study number theory?
     
  6. Jul 25, 2007 #5
    It depends what kind. The most basic concepts form Elementary Number Theory and can even be learned while still in high school.
     
  7. Jul 25, 2007 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    The implementation notes say that
    • PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.
    • As of 1997, this procedure is known to be correct only for n<1016, and it is conceivable that for larger n it could claim a composite number to be prime.

    I'm now re-running it using this package.
    [update]The kernel crashed and I need it for something else now. It ran for over an hour though. [/update]
     
    Last edited: Jul 25, 2007
  8. Jul 25, 2007 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Thanks, that looks good.

    I think the number is too long to reasonably prove prime, but it looks like we have shown it to be very likely to be a prime.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Double check - this is prime, yes?
  1. Prime double pairs. (Replies: 3)

  2. Checking Primes (Replies: 1)

  3. Prime Ideals (Replies: 1)

Loading...