Wednesday, February 17, 2021

[lkcpxgpw] Fermat number on the edge of GMP

the largest number GNU MP can represent is 2^2^37-1.  there is a somewhat interesting number just slightly smaller than the limit: (2^2^37+1)/(1275438465 * 2^39 + 1) = (2^137438953472+1)/701179711390136401921.  this is the 37th Fermat number with its one known prime factor divided out.  even though we wrote it as a fraction, the number is an integer, 41 billion digits.  (we don't know whether this remaining cofactor is prime or composite; it is too large to test.  it is probably composite.  the largest Mersenne prime, currently 20 million digits, demarcates approximately the largest number whose primality can be tested in a reasonable amount of time with current technology.)

incidentally, the number is a factor of 10^21 (or 2^69) smaller than 2^2^37-1; however, we are among such large numbers that a number that much smaller can still be called "just slightly smaller": 2^2^36.999999999496 is just slightly smaller than 2^2^37 .

representing this number requires 16 GiB of memory, not an unreasonable amount these days.  also, many multiprecision arithmetic operations in GNU MP do OK with swap memory.

computing this number is a little bit tricky because the numerator as beyond what GNU MP can handle.  one way (not tested):

1. a = 2^37-1
2. b = 2^a-1 (b = 2^(2^37-1)-1)
3. c = 2*b+1 (c = 2*(2^(2^37-1)-1)+1 = (2*2^(2^37-1)-2)+1 = 2^(2^37)-2+1 = 2^2^37-1 = largest number that GNU MP can represent)
4. m = 1275438465 * 2^39 + 1 = 701179711390136401921
5. (q,r) = divMod c m
6. verify that r == m-2

from (2^37*log(2)-log(m))/log(10) we know the number is approximately 7.806275851 * 10^41373247546 .  can its final digits (in any base) be extracted easily?