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.
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.