Smallest twin-prime-pair above $2\uparrow\uparrow 5\ $? I searched the smallest prime larger than $$N:=2\uparrow\uparrow 5=2^{65536}$$ $N$ has $19\ 729$ digits. This is quite large and finding primes of this magnitude is not easy any more.
I found $$N+44\ 061$$
This fits well to the fact that a number near $N$ is prime with probability $1:45\ 426$
But the next prime is surprisingly
$$N+44\ 181$$

Did I miss any primes ? In other words, are the other numbers from $N$ to $N+44\ 181$ composite ?

Even using the quite fast pfgw-prime-testing software, it took me about half a day to get those primes. So, I wonder whether we can calculate the smallest twin-prime-pair above $N$ (If this was not already done).

Does anyone have an idea how we can find the smallest twin prime pair above $N$ with a reasonable amount of time ?

The only idea I have is to sieve out the candidate-pairs by trial division, but there might be a better method.
 A: You didn't miss any.  With $n = 2^{65536}$, $n+44061$ is a PRP as is $n+44181$.  All other numbers from $n$ to $n+44181$ are composites.
There are no twin primes in the range $n$ to $n+10\ 000\ 000$.
To the best of my knowledge, the best way to do this is not dis-similar to what you've said:


*

*pick a range and sieve it.  Once into reasonable depths, the range length doesn't have a big performance impact, but the depth does.  For my test with your $n$ and a length of 10M, my program chose a default depth of 5243M, leaving about 8300 candidates after ~3 minutes.  It should have chosen to sieve deeper.  ~600 of those candidates drop out after just 6 more minutes of sieving.

*From the sieved range, candidates are those $n$ where $n$ and $n+2$ both have survived sieving.

*Run a fast compositeness test on them.  At this size PFGW's Fermat test is the most efficient.  That typically means running multiple programs running through intermediate files.  I use GMP throughout, which is more convenient, but not ideal performance for these over-10k-digit numbers.  I use a Miller-Rabin base 2 test, which is about the same speed as a Fermat test in GMP.

*Verify results if both pass the first test.  I use an ES Lucas test, which means the results are extra strong BPSW probable primes since I used a base-2 MR test to start.  If using PFGW, just run them through a BPSW test from one of the many packages that have a BPSW test (PFGW includes a version but you'd have to look up how to apply it).  This is enough for most purposes, but you can run a few more tests if desired.
