9
$\begingroup$

So, I have been playing around with prime numbers, I have installed gmp and gmpy2

gmpy2 has a function gmpy2.is_prime for primality testing (non deterministic) which uses the Miller-Rabin primality test.

Now to test the speed of gmpy2.is_prime I typed some random digits '1245268798719487981976914598618498569816481948' and added a '3' to the end so that the number is not even. It took it milliseconds to get the result and to my surprise,

In [18]: gmpy2.is_prime(12452687987194879819769145986184985698164819483)
Out[18]: True

What? really? the number I randomly typed is a prime?

To make sure is_prime wasn't returning true for every other number I added a few digits and expectedly

In [25]: gmpy2.is_prime(124526879871948798197691459861849856981648139483)
Out[25]: False

In [26]: gmpy2.is_prime(12452687987194879819769145986555184985698164819483)
Out[26]: False

I was blown away, but now, I am curious. What is the probability of this happening?

More specifically, What is the probability that a randomly selected odd 47 digit number passes Miller-Rabin primality test?

Did I just get really really lucky?

$\endgroup$
5
  • $\begingroup$ Less than 40%, since any number ending in 2, 4, 5, 6, 8, or 0 will not be prime, but actually much lower than that. $\endgroup$
    – torazaburo
    Dec 14, 2014 at 5:39
  • 3
    $\begingroup$ @torazaburo that is really optimistic $\endgroup$
    – Optimus
    Dec 14, 2014 at 5:39
  • 1
    $\begingroup$ @StephenC thanks... that answers it, I did not get that lucky either log(12452687987194879819769145986555184985698164819483) = 113.046.., 1 in 113 is not that lucky... $\endgroup$
    – Optimus
    Dec 14, 2014 at 5:48
  • 3
    $\begingroup$ The 1 / log(x) probability estimate includes even numbers. The probability that an odd number is prime is about 2 / log(x). $\endgroup$ Dec 14, 2014 at 11:42
  • 1
    $\begingroup$ If you made sure that the last digit is $1,3,7 \ or\ 9$ you have a slightly higher probability, about $\frac{2.5}{\ln(x)}$ , which is about $1$ out of $42$ in your case. $\endgroup$
    – Peter
    Sep 4, 2019 at 9:51

1 Answer 1

6
$\begingroup$

According to Prime number theorem there are approximately $$10^{47}/\ln(10^{47}) - 10^{46}/\ln(10^{46}) = 8.296\cdot10^{44}$$ 47-digit primes and $$9\cdot10^{46}/2$$ odd 47-digit numbers. So the probability is approximately $8.296\cdot10^{44}/4.5\cdot10^{46} = 0.018$.

Without numbers with 5 as last digit the probability is approximately $8.296\cdot10^{44}/3.6\cdot10^{46} = 0.023$.

Edit:

The values with the somewhat better approximation $1/\ln(x)$ for the probability that a random integer not greater than $x$ is prime are

$0.01868$ for odd number in the given range and

$0.02335$ for odd numbers not ending with 5.

$\endgroup$
2
  • $\begingroup$ Li(x) would be a better approximation to pi(x), and OP also excluded numbers ending in 5, so you need to divide by 2.5. $\endgroup$
    – gnasher729
    Mar 13 at 18:56
  • $\begingroup$ The question was "What is the probability that a randomly selected odd 47 digit number passes Miller-Rabin primality test?" (Strong pseudoprimes are rare enough to neglect them.) $\endgroup$
    – Eberhard
    Mar 13 at 19:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .