How to print the largest prime number found so far?

Question

On january the 19th a new world record was established: the one of the largest prime number found so far. The number amounts to 2^74207281 - 1 and has over 22.3 million digits. I saw on the numberphile channel on youtube that they printed this number in a 3-part book. Now my question is: how do you get a string representation of a number which is so large? Obviously this will take quite some time, but what is the most efficient way of doing this?

The only way I would know to do this in Java is by using BigIntegers, is this the best way? How about in other languages?

Answer 1

The only way I would know to do this in Java is by using BigIntegers, is this the best way?

In short

The answer to your question is: YES.

---

In detail

I think java and BigInteger is the best solution. A minimal example could look like this:

public class Prime {

    public static void main(String[] args) {
        BigInteger number = new BigInteger("2")
                .pow(74207281)
                .subtract(new BigInteger("1"));
        System.out.println(number);
    }

}

---

In even more detail

Maybe it's a good idea to let your computer print the numbers in small groups, instead of creating one, huge, String - for better performance:

import java.io.File;
import java.io.FileOutputStream;
import java.math.BigInteger;
import java.util.LinkedList;

public class Prime {

    private static final BigInteger THOUSAND = new BigInteger("1000");

    public static void main(String[] args) throws Exception {
        BigInteger number = new BigInteger("2")
                .pow(74/*207281*/) // use 74207281 for the real number
                .subtract(new BigInteger("1"));

        System.out.println("calculation done, creating texts");

        int counter = 0;

        LinkedList<String> threes = new LinkedList<>();

        for (;;) {

            // divide by 1000 to get next 3 digits
            BigInteger[] divideAndRemainder = number.divideAndRemainder(THOUSAND);
            number = divideAndRemainder[0];
            BigInteger lastThreeDigits = divideAndRemainder[1];

            // format digits, with leading zeros
            String text = String.format("%03d", lastThreeDigits);

            // add them to the list
            threes.addFirst(text);

            // stop, if we reached the end
            if (number.signum() == 0) {
                break;
            }

            // print progress
            if (counter++ > 999) {
                System.out.print(".");
                counter = 0;
            }
        }

        System.out.println("\ntexts ready, writing to file");

        counter = 0;
        try (FileOutputStream output = new FileOutputStream(new File("C:\\temp\\bignumber.txt"))) {
            for (String text : threes) {
                output.write(text.getBytes());
                output.write(' ');

                // print progress
                if (counter++ > 999) {
                    output.write('\n');
                    System.out.print(".");
                    counter = 0;
                }
            }
        }

        System.out.println("\ndone");
    }

}

Answer 2

You don't actually need to store the whole number as a string before printing it to a file. You just need to output each digit one by one.

As for representing the number itself in memory; that's a different matter. There are efficient ways of storing and manipulating large numbers of the Mersenne form: you wouldn't want to rely on a canned large integer class (such as BigInteger in Java) for doing that. The necessary mathematical operations for primality testing would be too slow.

There are far more comprehensive details in the GIMP project. See http://www.mersenne.org/

Answer 3

On a Linux system it is quite easy to achieve:

echo "2 74207281 ^ 1 - p" | dc > /tmp/74207281.txt

The file is --not surprisingly-- about 22 MB in size. On an i7 it took about 45 minutes to calculate. Not timed exactly.

By the way, 74207281 is a prime itself as well, according to Mersenne's theorem.