Consider numbers of the form $2^n - 2^k - 1$ with $k < n$ as considered in OEIS sequence A208083. As for A208083 I investigated how many of these numbers are prime, but turned the question around: For which numbers $n$ there are $m = 0,1,2,\dotsc$ numbers $k < n$ such that $2^n - 2^k - 1$ is prime. This is the result for $n \leq 28$:

\begin{align*} n(0) & {}= \{ 1, 2, 7, 15, 23, 27 \} \\ n(1) & {}= \{ 11, 13, 19, 25, 28\} \\ n(2) & {}= \{ 3, 5, 17, 26\} \\ n(3) & {}= \{ 4, 10, 16\} \\ n(4) & {}= \{ 6, 9, 21\} \\ n(5) & {}= \{ 8, 12, 14, 22\} \\ n(7) & {}= \{ 24\} \\ n(9) & {}= \{ 18\} \\ n(12) & {}= \{ 20\}. \end{align*}

I tried to see a pattern: which $n$ belong to a given $m$? I started by checking if there is an OEIS sequence starting with $n(0) = \{1, 2, 7, 15, 23, 27, \dotsc\}$. But without success. Neither for $n(1) = \{11, 13, 19, 25, 28, \dotsc\}$.

I also entered the sequence of arguments of $n(m)$, i.e. $\{0,1,2,3,4,5,7,9,12,\dotsc\}$. There are seven OEIS sequences starting with this sequence, but all of them are rather arcane. Only one seems related to prime numbers: A214120, Number of Proth primes < 2^n.

I wonder nevertheless if there are first-order characterizations of the above sequences. At least: if it can be shown that all $n \in n(m)$ are even when $m>1$ is odd.

More specifically I'd like to know if $n(m) \neq \emptyset$ for all $m$ – and if there can be $m$ with finite $|n(m)|$.

And are Proth primes really related to this problem? (Probably not.)