## Sunday, May 31, 2020

### [mcybbfcw] Some Cunningham chains

Let f(x)=(x-1)/2 .  Below are some numbers p such that p, f(p), f(f(p)), f(f(f(p))),... are prime.  The first offset is the first prime after 2^n.  The second offset is the first safe prime after 2^n.  The third offset has p, f(p), and f(f(p)) all prime, and so forth.

These searches could be sped up by some analysis of remainders, but we do not do these optimizations in the code below.

Not sure what these primes might be useful for.  Even the safe primes are too small to use for secure cryptography (discrete logarithm).

primelevel(p)=my(l=0) ; while(p>=2 , if(ispseudoprime(p) , l+=1 ; p=(p-1)/2 , break)) ; l

? start=2^64 ; best=0 ; for(i=start , +oo , v=primelevel(i) ; if(v>best , best=v ; print(v," ",i-start)))

2^64 +13 +3103 +20911 +7391983 +29472223 +1161518143 +25033718143

2^128 +51 +12451 +531511 +48965743 +311484703

2^256 +297 +230191 +8333983 +894039583 +96241401343

We also investigated starting from zero.  The sequence begins 2 5 11 23 47 2879 71850239 2444789759 21981381119.  Not sure about the last entry because we only searched among x mod 480 = 479.  This sequence is almost the same as OEIS A110056, but we don't require Cunningham chains to be complete (not able to be extended in either direction).  Tangentially, A110056 is currently not in sync with A005602.  Assuming A005602 is correct, A110056 is missing an additional term 1484656016727504358932479.