Mersenne Prime # of Digits Calculator

[R.D. Silverman]

Originally Posted by drew

What about those of us who already know how to perform the calculation? Should we not use software to make it simpler for us? Should I derive my own logarithm tables myself?

What's the matter? Is a hand calculator too complicated a tool for you?
If you know how to do the calculation, then a specialized program
is not needed. Nor is it any faster.

[Jeff Gilchrist]

Originally Posted by R. Gerbicz

There are numbers less than 2^64 for which your program is bad:
for example: p=28505944177 (this p is prime)
or for p=198096465 (this p is composite) gives bad number of digits for 2^p-1

You are absolutely right. It seems there were some rounding errors which I have now fixed so hopefully everything will be accurate now. Thank you for finding those problems so I could fix them.

I have now released v1.1 available from:
http://gilchrist.ca/jeff/MprimeDigits

New in v1.1:

• Fixed rounding errors reported by R. Gerbicz.
• Command line version now accepts multiple p values on the command line (ie: mprimedigits 32582657 25964951)
• Now displays formula used to calculate # of digits so people can better understand how to calculate it themselves if they wish.

As for Dr. Silverman's comments, I originally wrote this program for myself just to make it easier to calculate with 1 button push instead of several, but I figured others on the Internet in general would be interested as well so it is now available for anyone to use. In order to help people learn if they wish, I have now included the formula the program uses as a starting point for them instead of it being a complete black hole.

[Jeff Gilchrist]

Originally Posted by R.D. Silverman

What's the matter? Is a hand calculator too complicated a tool for you?
If you know how to do the calculation, then a specialized program
is not needed. Nor is it any faster.

Well it is faster in the sense that with my program you can use a script to pass it multiple values to calculate at once, giving you all the results in probably the same amount of time it would take to use a hand calculator for one number.

[ewmayer]

Using the unix/linux bc utility [or a decent electronic calculator with any form of a "log" function], it's trivial: start "bc -l" [the -l flag invokes floating-point mode], then

[your exponent here]*l(2)/l(10)

..and round up. The -1 subtracted from the 2^p in the real Mersenne number is nearly always ignorable if the the digit count is large - you'd only need to include it if the above result is really, really close to a whole number. ["How close" makes for a nice homework assignment.]

Example: for p = 32582657, the above gives 9808357.095430986538..., which is not close to a whole number in the relevant sense, so we round confidently up and get 9808358 decimal digits for M44.

[lavalamp]

Originally Posted by ewmayer

The -1 subtracted from the 2^p in the real Mersenne number is nearly always ignorable

For a Mersenne number it is always ignorable, since 2^n mod 10 can only equal 2, 4, 6 or 8.

Edit: When finding the number of digits for a number such as 5^n*2^n - 1 though, the minus one does matter.

[R. Gerbicz]

Originally Posted by Jeff Gilchrist

I have now released v1.1

For large inputs your program is still bad (see the picture).

My c solution for the problem, no trick, not using built in large math libraries:
( it should be good for p<10^40 )

#include <stdio.h>
#include <string.h>


int main()  {

    int A[40],B[100],R[141],carry,valid,i,j,L;
    char input[64],w[101]="3010299956639811952137388947244930267681898814621085413104274611271081892744245094869272521181861720";
    
    while(1)  {
          printf("Please input an exponent (at most 40 digits) : ");
          scanf("%s",input);
          L=strlen(input);
          valid=1;
          for(i=0;i<L;i++)
              if((input[i]<'0')||(input[i]>'9'))  valid=0;
          if((valid==0)||(L>40))  printf("Invalid input!\n");
          else break;
    }
    
    for(i=0;i<L;i++)    A[i]=input[L-1-i]-'0';
    for(i=0;i<100;i++)  B[i]=w[99-i]-'0';
    for(i=0;i<141;i++)  R[i]=0;
    // grammar school multiplication
    for(i=0;i<L;i++)
        for(j=0;j<100;j++)  R[i+j]+=A[i]*B[j];
    
    R[100]++;
    carry=0;
    for(i=0;i<=140;i++)  {
        carry+=R[i];
        R[i]=carry%10;
        carry/=10;
    }
    
    i=140;
    while(R[i]==0)  i--;
    printf("The number of decimal digits of 2%c%s%c1 is ",'^',input,'-');
    while(i>=100)  printf("%d",R[i]),i--;
    printf("\n");
    return 0;
}

[jrk]

Originally Posted by R. Gerbicz

char input[64]

scanf("%s",input);

Careful with that. You don't want to write more than 64 bytes to "input".

[akruppa]

On a side note, if you want to do the (approximate) conversion with pencil and paper, a useful fact to remember is that
F₁₂ has 1234 decimal digits.

Conveniently, the leading digits of F12 are 104..., so 2^4096 is pretty close to 10^1233, and the estimate
log(10)/log(2) ~= 4096/1233 = 3.3219...
is reasonably accurate. From the continued fraction expansion the better fraction 2136/643 = 3.321928... can be found, but it's not as easy to remember.

Alex

[R.D. Silverman]

Originally Posted by akruppa

On a side note, if you want to do the (approximate) conversion with pencil and paper, a useful fact to remember is that
F₁₂ has 1234 decimal digits.

Conveniently, the leading digits of F12 are 104..., so 2^4096 is pretty close to 10^1233, and the estimate
log(10)/log(2) ~= 4096/1233 = 3.3219...
is reasonably accurate. From the continued fraction expansion the better fraction 2136/643 = 3.321928... can be found, but it's not as easy to remember.

Alex

Also, the utility of this tool somehow eludes me. Why would someone
who doesn't know how to do the calculation need to know how many
digits 2^p-1 has?

[xilman]

Originally Posted by R.D. Silverman

Also, the utility of this tool somehow eludes me. Why would someone
who doesn't know how to do the calculation need to know how many
digits 2^p-1 has?

You are confusing "need" and "want".

An adequate justification for wanting to know is idle curiosity.


Paul

[R.D. Silverman]

Originally Posted by xilman

You are confusing "need" and "want".

An adequate justification for wanting to know is idle curiosity.


Paul

Not where I work.............