1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...