# Which $n$ have $\lvert\{2^n-2^k -1\}\cap {\mathrm{PRIMES}}\rvert=m$?

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

• I don't see hope for characterizing the preimage of $f$ where $f(n)=|\{ 2^n -2^k-1\}\cap \textrm{PRIMES}|$. What could probably be done is to obtain some probabilistic model for the values of $f$. E.g. Cramér's model suggests $f(n)$ behaves (roughly) like a sum of independent Bernoulli variables $B_1,\ldots,B_{n-1}$ with $\mathbb{P}(B_i=1)=1/\log(2^n-2^i-1)$. There are models such as Granville's model that take into account dependency among small primes and can be used to refine this simplistic prediction. Sep 16, 2022 at 19:30
• I do not see any reason any $m$ cannot be attained. 28 is an extremely small sample; a rough model for how large $n$ you should take to see all values of $m$ up to $M$ attained is given by the coupon collector problem (which you can adapt with some work to your problem in which you morally sample a Poisson distribution and want to obtain certain values). Sep 16, 2022 at 20:19
• The sequence A208091 gives the smallest member in each $n(m)$. It appears to be unknown whether $n(21)=\emptyset$ or not. Dec 20, 2022 at 15:10

The conjecture is false, eg with $$m=5, n=29$$ or $$m=3, n=49$$. Here is some R code, which I ran online at rdrr:
f = function(n)sum(gmp::isprime(2^n-1-2^(1:(n-1)))/2)