{"id":54,"date":"2022-11-01T12:00:00","date_gmt":"2022-11-01T12:00:00","guid":{"rendered":"https:\/\/blog.marcinpolkowski.com\/?p=54"},"modified":"2022-12-03T01:38:30","modified_gmt":"2022-12-03T01:38:30","slug":"how-to-calculate-the-value-of-the-biggest-prime-we-know","status":"publish","type":"post","link":"https:\/\/blog.marcinpolkowski.com\/?p=54","title":{"rendered":"How to calculate the value of the biggest prime we know?"},"content":{"rendered":"

I hope that I don’t need to introduce prime numbers to anyone. They are fascinating for all mathematic enthusiasts. We know a lot of prime numbers, but we have no formula to calculate them. Search for the biggest primes is an ongoing competition. People are looking for the biggest primes among the so-called Mersenne Primes. Mersenne Primes are primes that can be expressed as 2n<\/sup>-1. The record is currently held by 282,589,933<\/sup>\u22121 with 24,862,048 digits, found by GIMPS in December 2018 (more on Wikipedia<\/a>).<\/p>\n

We can find a value of 282,589,933<\/sup>-1 online (for example beginning and the end of the number on Wikipedia linked above). But what if we would like to calculate the value ourselves? We have multiple options. For the sake of this article, I selected 2:<\/p>\n

bc – an arbitrary precision calculator language<\/h3>\n

bc<\/b> is a linux\/unix command line calculator that supports arbitrary precision:<\/p>\n

<\/a><\/center><\/p>\n

We can run the following in the terminal to calculate the value of 282,589,933<\/sup>-1. We use tr and sed to pack the result in one line.
\n

<\/p>\n
echo \"Testing BC:\"\ntime echo \"2^82589933-1\" \\\n    | bc \\\n    | tr \"\\n\" \" \" \\\n    | sed 's\/\\\\ \/\/g' \\\n    > bc.txt\n<\/code><\/pre>\n
<\/center>
\nSince the calculation is not trivial the answer is not coming instantaneously. On my 2021 MacBook pro with M1 Max processor it took 30 minutes to get the result: >24 megabytes of digits.<\/p>\n
Python<\/h3>\n
Yes, Python! Python supports arbitrary precision integers by default. There is a slight complication that was added recently for security reasons: we need to increase the default length of the number that can be converted to a string. Let’s consider the following code:
\n
<\/p>\n
import sys\nsys.set_int_max_str_digits(int(3e7))\n\nnumber = 82589933\n\nprint(2**number-1, end=' ')\n<\/code><\/pre>\n
<\/center><\/p>\n
And run it in the terminal:
\n
<\/p>\n
echo \"Testing Python\":\ntime python python.py > python.txt\n<\/code><\/pre>\n
<\/center><\/p>\n
It takes python almost 3 hours to compute the result.<\/p>\n
Results<\/h2>\n
Finally, we can confirm that both results are the same:
\n
<\/p>\n
echo \"Comparing Results\":\nshasum bc.txt\nshasum python.txt\n<\/code><\/pre>\n
<\/center><\/p>\n
Which should give result as following:
\n
<\/p>\n
Comparing Results:\n9abebcdaf11efd28f1797d6b2744cbcb0cc66e52  bc.txt\n9abebcdaf11efd28f1797d6b2744cbcb0cc66e52  python.txt\n<\/code><\/pre>\n
<\/center><\/p>\n
Summary<\/h3>\n
If you ever need to calculate integers bigger then 64 or 128 bits, now you know how.<\/p>\n","protected":false},"excerpt":{"rendered":"
I hope that I don’t need to introduce prime numbers to anyone. They are fascinating for all mathematic enthusiasts. We know a lot of prime numbers, but we have no formula to calculate them. Search for the biggest primes is an ongoing competition. People are looking for the biggest primes among the so-called Mersenne Primes. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,6],"tags":[],"class_list":["post-54","post","type-post","status-publish","format-standard","hentry","category-linux","category-python"],"_links":{"self":[{"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/posts\/54","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=54"}],"version-history":[{"count":8,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/posts\/54\/revisions"}],"predecessor-version":[{"id":63,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=\/wp\/v2\/posts\/54\/revisions\/63"}],"wp:attachment":[{"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=54"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=54"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.marcinpolkowski.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=54"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}