Math

New prime on the block

by Christian S. Perone

The GIMPS (Great Internet Mersenne Prime Search) has confirmed yesterday the new largest known prime number: 277,232,917-1. This new largest known prime has 23,249,425 digits and is, of course, a Mersenne prime, prime numbers expressed in the form of 2n – 1, where the primality can be efficiently calculated using Lucas-Lehmer primality test.

One of the most asked questions about these largest primes is how the number of digits is calculated, given the size of these numbers (23,249,425 digits for the new largest known prime). And indeed there is a trick that avoids you to evaluate the number to calculate the number of digits, using Python you can just do:

>>> import numpy as np 
>>> a = 2
>>> b = 77232917
>>> num_digits = int(1 + b * np.log10(a))
>>> print(num_digits)
23249425

The reason why this works is that the log base 10 of a number is how many times this number should be divided by 10 to get to 1, so you get the number of digits after 1 and just need to add 1 back.

Another interesting fact is that we can also get the last digit of this very large number again without evaluating the entire number by using congruence. Since we’re interested in the number mod 10 and we know that the Mersenne prime has the form of 277,232,917-1, we can check that the powers 2n have an easy cycling pattern:

2^1 \equiv 2 \pmod{10}
2^2 \equiv 4 \pmod{10}
2^3 \equiv 8 \pmod{10}
2^4 \equiv 6 \pmod{10}
2^5 \equiv 2 \pmod{10}
2^6 \equiv 4 \pmod{10}
(… repeat)

Which means that powers of 2 mod 10 repeats at every 4 numbers, thus we just need to compute 77,232,917 mod 4, which is 1. Given that 2^{77,232,917} \equiv 2^1 \pmod{10} the part 277,232,917 ends in 2 and when you subtract 1 you end up with 1 as the last digit, as you can confirm by looking at the entire number (~10Mb zipfile).

– Christian S. Perone