Is it intractable to locate a sequence of prime/not-prime bits? For $n \in \mathbb{N}$, Let $p(n) = 1$ if $n$ is prime and $p(n) = 0$ otherwise.  Roughly, my question is
Rough question: Given a rough estimate of $n$ and a sequence $p(n), p(n+1), \ldots, p(n+k-1)$ for $k = \log^{O(1)} n$, is it intractable to compute $n$?
To make this concrete, let $k = k(n) = \lfloor \log^{\alpha} n \rfloor$ for some exponent $\alpha > 1$.  Our task is
Task: Given $n$ and a sequence of bits $b_0, \ldots, b_{k-1}$, find $m \in [n, 2n]$ s.t. $p(m+i) = b_i ~\forall i$, or report failure if none exists.
What's the computational complexity of this task as a function of $\alpha$?  Is it always polynomial in $\log n$?  Notes:

*

*For this to be interesting, we have to set $\alpha$ high enough that the $m$ is likely unique.

*I'm looking for conjectural complexity only, especially if the answer is "probably intractable", as I expect it to be hopeless to prove anything in this direction.

 A: This isn't a solution, but is too long for a comment.
We would expect that an actually occurring bit sequence typically has roughly $\frac{k}{\log n}$ $1$'s. So let's say that we have  the set $S=\{i<k \mid b_i=1\}$.
If $|S|$ is sufficiently small then we would very strongly suspect that no $m \in [n,2n]$ gives that $S$. But ruling it out might be very hard. For example if $n=10^{100},$ $\alpha=3$ :

*

*Is there an $m$ giving  $S=\emptyset$?

*Is there an  $m$ giving any $S$ of cardinality $5$ or less?

After all, one doubts that there is an interval $[t^2,(t+1)^2]$ devoid of primes, but no proof is available.
On the other hand, if $k$ isn't too small, and $S$ comes from an actual $m$, then it might usually be relatively easy to to find an $m$ giving that $S$. For a given prime $p$, each $s \in S$ rules out one possible value for $m \bmod p.$ This might be enough to specify the actual value of $m \bmod p$ (or restrict it to a few possibilities.) I illustrate this wild speculation with a single example:
Suppose $n=2 \cdot 10^{10}$ and $k=2000< \log n^{2.5}.$ For the randomly chosen case of $m=314159265358$ it turns out that $S$ has $73$ members. (On average, we would expect around $84$ members). The first ten members are $ 1, 31, 33, 39, 63, 91, 159, 169, 219, 235$ These reveal that $n \bmod [2,3,5,7] =[0,2,2,6].$ The full set reveals the congruence class of $m$ for all primes up to $23$ and also for $31.$ Since those primes multiply to about $7\cdot 10^9,$ that allows only one , or perhaps two, values of $m$ in the range. Also we can tell that $m \bmod 29 \in \{6,25\}.$
Note that the only information needed is "which congruence classes $\bmod p$ are represented at all? For primes $p \leq 31$" and that restricts $m$ to two possible congruence classes $\bmod 200560490130$
On the other hand, in that example, here are two congruence classes $\bmod 17$ which are ruled out by only one witness and one each for $19$ and $23$. So removing those four increases the the number of possible congruence classes by a factor of $12.$ That kind of selective trimming in a larger example could create a plausible looking $S$ which leaves many candidates for $m$ , none of which end up working.
