Least number $k>11$, such that $k+n$ is prime for $n=0,2,6,8,12,18,20,26,30,32$

Question

The least integer $k>11$, for which $k+n$ is prime for $n=0,2,6,8,12,18,20,26,30,32$, is, according to my search, $k=33,081,664,151$.

The numbers form a prime constellation with length $10$ and width $32$.

$1)$ Is my number the smallest one ?

$2)$ How can the smallest number be found without brute force ?

Looking at the residue classes $2$,$3$,$5$ and $7$, I found out that $k$ must be of the form $210k+11$, but I did not get further restrictions for $k$. Of course, I could continue with the residue classes modulo $11,13,... $. Is this the best and only way to restrict $k$, or are there more powerful methods ?

Answer 1

Your questions made me go do some work on this. It's not released yet, but on github.

time perl -Mbigint -Mntheory=:all -E 'say join " ", Math::Prime::Util::GMP::sieve_prime_cluster(1,1e11, 2,6,8,12,18,20,26,30,32);'
11 33081664151 83122625471

real    0m0.161s
user    0m0.148s
sys     0m0.011s

time perl -Mbigint -Mntheory=:all -E 'say join " ", Math::Prime::Util::GMP::sieve_prime_cluster(1e19,1e19+1e13, 2,6,8,12,18,20,26,30,32);'
10000005800403630281

real    0m8.096s
user    0m8.081s
sys     0m0.012s

In some examples I've looked at, polysieve2 is slightly faster, assuming you tune the sieve sizes. Bad sieve size choices can make it much slower. It quite likely is much faster on some other cluster combinations. Your mileage may vary. The times from JKA's posts suggest his old code is very fast. There are some OEIS sequences for long clusters that imply someone either had a lot of time or has a really fast program.

1. Use a primorial, e.g. 23# to generate a list of acceptable residues. I try to choose an appropriate primorial size, stopping at 23# (to keep all residues under 31 bits) or earlier if we have more than ~50k residues or the given range is small. But you could just pick something. Matt Anderson uses 13# (30030) for his examples, JKA uses 31#. Larger primorials are more efficient but the overhead starts growing.
2. Walk through the range in chunks of the primorial size. We'd like to efficiently sieve further, which can be done using only the base+residue locations. For primes larger than the primorial prime and the chosen depth (e.g. 1000), we can check divisibility of the offset residues. If dealing with bigints this is especially nice as only a single bigint modulo is needed per prime, with the rest all being 32-bit calculations. With a large range you could optimize a bit more and do some of these modulos once before you start walking the range then simple boolean computations can be done for a few of the first primes. I'm doing that and it really helps. polysieve2 is quite fast at this step.
3. Do primality tests on the residues that are left. Step 1 guaranteed that none of the locations checked have factors <= your primorial prime. Step 2 made sure nothing has factors under your sieve depth. polysieve2 doesn't do this step, meaning you use something else for the final tests.

Step 2 is where most of my time is spent, but of course it's more efficient to at least spend some time there. Step 1 is pretty straightforward, and if you have a favorite cluster you can do it once by hand if you desired. This simple thing greatly reduces the number of tests needed. For this cluster, step 1 gets us down to 8190 residues per 223092870 values. Step 2 reduces this to under 5 residues left on average with a depth of 1000. Step 3 does the final check. For the second example (10^19 to 10^19+10^13) it ended up doing 289341 total BPSW tests. Typically this is a small part of the time (but may be quite large if the numbers are huge).

The details vary, but I think most of the programs I've seen go through those steps. 1. Use a primorial to find acceptable residues. 2. As we walk the range in primorial-sized steps, sieve further to reduce even more. 3. Primality tests.

Answer 2

You say you got nothing beyond k = 210n + 11, but we also know that k modulo 11 is 6 or 8, which makes k = 2310n + 1271 or 2310n + 1691, and there are only 5 values modulo 13, so there are 10 values modulo 30,030. Plus 7 values modulo 17, so there are 70 values modulo 510,510, or one in 7293.