next up previous
Next: Computing signatures of logarithms Up: A better method for Previous: Simple algebraic relations

Primes suitable for nested exponentials

In general, if we want to handle several levels of nested exponentials, we will have to precompute several primes n1, n2, ... so that ni+1 = 4kini+1. This will make it possible to represent i at all levels. The values of ki should be chosen as small as possible, as we want to keep the ratio between the largest and smallest primes small. The following Maple code generates a sequence of 5 primes with this property. It should be noticed that the ratio between n5/n1 = 1536. The minimum ratio, for all ki=1, or 256 is not attainable.
n1 := 10^9:
maxn5 := n1*10^10:

to 10000 do
  n1 := nextprime(n1);
  if modp(n1,4) = 1 then for n2 from 4*n1+1 by 4*n1 while 64*n2+21 < maxn5 do
    if isprime(n2) then for n3 from 4*n2+1 by 4*n2 while 16*n3+5 < maxn5 do
      if isprime(n3) then for n4 from 4*n3+1 by 4*n3 while 4*n4+1 < maxn5 do
        if isprime(n4) then for n5 from 4*n4+1 by 4*n4 while n5 < maxn5 do
          if isprime(n5) then
            maxn5 := n5;
          fi od fi od fi od fi od fi od:
The best set of primes found with the above is 1000077157 4000308629 48003703549 192014814197 1536118513577.

Gaston Gonnet