The Biggest Prime

February 8, 2013

This is a simple program:

> (with-output-to-file "bigprime.txt"
    (lambda ()
      (display (- (expt 2 57885161) 1))))

However, when I ran that program, the machine thrashed for a while, and after about a minute, crashed. So I wrote this program using C/GMP, which can be compiled with the command gcc bigprime.c -lgmp -o bigprime:

/* bigprime.c -- save the digits of 2^57885161-1 to a file */

#include
#include "gmp.h"

void main(void)
{
    mpz_t p;
    FILE *fp;
    fp = fopen("bigprime.txt","w");
    mpz_init(p);
    mpz_ui_pow_ui(p, 2, 57885161);
    mpz_sub_ui(p, p, 1);
    gmp_fprintf(fp, "%Zd", p);
    mpz_clear(p);
    fclose(fp);
}

The program ran successfully, creating the bigprime.txt file in about a minute. You can see the program at http://programmingpraxis.codepad.org/xbg11nxk.

About these ads

Pages: 1 2

12 Responses to “The Biggest Prime”

  1. danaj said

    From the command line:

    perl -E 'use bigint lib=>"GMP"; say 2**57_885_161-1'
    

    redirect to a file if you’d like. Produces 17,425,171 digits in under 5 seconds on my machine.

    Using the Pari backend requires raising the Pari stacksize — I didn’t try it. Using the default Calc backend is quite slow as expected with very big numbers — I killed it after 7 minutes.

  2. Justin said

    Fabrice Bellard’s solution to a smaller Mersene can be found here : http://bellard.org/mersenne.html

  3. Globules said

    Haskell:

    main = print $ 2^57885161-1
    
  4. Paul said

    The first attempt using Python 2.7 failed. It is no problem to make the prime, but printing it (or converting it to a string) takes more than 2 hours (and maybe never finishes). Using the gmpy library the time taken is 22 secs. It creates a file of about 17 MB.

    import gmpy
    out = open("bigprime.txt", "w")
    n = gmpy.mpz(2 ** 57885161 - 1)
    out.write("{}".format(n))
    out.close()
    
  5. [...] ¿cuáles son todas las cifras del primo 48 de Mersenne? En erl sitio Programming Praxis se reta a los lectores (programadores) a que generen los 17 millones de dígitos. Un programa [...]

  6. [...] el sitio http://programmingpraxis.com/2013/02/08/the-biggest-prime han publicado un reto para escribir los un poco más de 17 millones de dígitos que tiene el 48o [...]

  7. bitchef said

    I had to use the GMP C Library.
    There exists a function to specifically do this sort of thing. Here is my code in C :

    #include <gmp.h>
    int main(){    
        mpz_t one;
        mpz_t op1;
        long op2 = 57885161 ;
        mpz_t temp;
        mpz_t result;
        
        mpz_init(one);
        mpz_init(result);
        mpz_init(temp);
        mpz_init(op1);
        
        mpz_set_ui(op1, 1);
        mpz_set_ui(one, 1);
        mpz_mul_2exp(temp , op1, op2);
        mpz_sub(result , temp, one);
        
        gmp_printf("The biggest prime number  is \n %Zd\n " , result );
    

    Redirecting the big prime to a file produces a 16.6 Mb file on my machine. It runs in under 3 seconds on my old laptop with a Pentium 4 processor.

  8. kbob said

    I decided to print it in hex. (-:

    >>> def pmx(n): return '137'[:n % 4][-1:] + 'f' * (n / 4)
    ... 
    >>> print pmx(57885161)
    
  9. razvan said

    What I found out today is that Standard ML’s big integer library appears to be horrifically slow.
    The code is:
    [sourrcecode]
    Control.Print.intinfDepth := 17500000;
    IntInf.pow (LargeInt.fromInt 2, 57885161) – 1;
    [/sourcecode]
    It’s still running after about 5 hours.

  10. […] trying to solve the biggest prime programming praxis problem in C#. The problem is simple, print out or write to file the number: […]

  11. Christo said

    Globules said
    February 9, 2013 at 8:07 AM

    Haskell: 1 main = print $ 2^57885161-1

    581887266232246442….. Wrong!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: