how do you know it is never a prime? context please

Have you looked at the example at rieselprime.de/ziki/Sierpiński_problem? That should give you some sense of what shape a covering set is likely to have: look for small arithmetic progressions in the exponent $n$. The useful prime divisors will tend to be ones that divide $2^n-1$ where $n$ itself has small prime divisors, e.g. $73$ divides $2^9-1$.

@Mike proof by authority :) I read it somewhere from a reliable source.

@ErickWong yes I was aware of that. But thanks for the nice link anyway +1

@mick You said you had no idea how to look for a covering set :).

@ErickWong I was modest. In your example mod 36 works but the 36 is a mystery ... Easily found lucky small number than works perhaps. Maybe this one is harder.

Interestingly, $1518781 = 2\cdot 15^5 + 31$. Maybe it helps?

Trying and using several modulos, assuming I haven't made any mistakes, I so far have that $n \equiv 0 \pmod{24}$ for the expression to possibly be prime.

since $1518781 = 1 \bmod 3$, all odd $n$ will give $2^n = 2 \bmod 3$ and hence sum not prime. We can carry on in similar fashion perhaps.

FYI, doing a site search for $1518781$, there's this answer which uses that number in a solution to a somewhat similar question to yours.

At least empirically (testing up to $n = 100000$ by finding the smallest prime that divided the expression for each $n$), it seems that the covering set is $\{3, 5, 7, 13, 17, 23, 29, 31, 47, 83, 89, 131, 137, 149, 163, 167, 227, 239, 241\}$. I did originally try a bunch of modulos, but it seemed like either a whole lot of case work or just an ugly search for primes after reducing modulo $3$ and $5$.

You can get it down to $\{3,5,7,13,17,241 \}$

Thanks guys. These comments combined are an answer. It is a bit of puzzling though. Is there no systematic way ? Maybe there is a theorem for upperbounds of the size of the covering map ?

@Sil This is exactly the covering set used by Pomerance in the slides I linked.

You have t proven it for all non-multiples of $3,$ so I thing your reduction to $8^n+\dots$ is wrong.

Rather, you want $16^n+\dots.$

Follows by a standard covering congruence argument, as in the linked dupes (here you need only check the first $24$ factorizations).

For reference $\,2^{24}-1 = 3^2\ 5\ 7\ 13\ 17\ 241\ $ yields the covering primes. See [here](math.stackexchange.com/a/1153492/242) in the dupe for a proof of why it works (se the comments there for how to discover that $24$ works - its quite simple once you understand the idea).

How is $19 * 8^n + 17 $ a duplicate of $2^n + 1518781$ ???

@BillDubuque why is it of the form $2^n - 1$ ?