6
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ofir Gorodetsky
    Sep 16, 2022 at 19:30
  • 2
    $\begingroup$ 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). $\endgroup$
    – Ofir Gorodetsky
    Sep 16, 2022 at 20:19
  • $\begingroup$ The sequence A208091 gives the smallest member in each $n(m)$. It appears to be unknown whether $n(21)=\emptyset$ or not. $\endgroup$
    – Pontus von Brömssen
    Dec 20, 2022 at 15:10

1 Answer 1

Reset to default
7
$\begingroup$

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)
counts = lapply(1:64, f)
lapply(1:64, function(m)which(counts==m))
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.