Prime numbers of the form $(2^k)p+1$, for a given prime $p$ Let $p$ be a prime. (say 256 bit)

Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such a $q$ exist.

[I know it exists for k =1, I am looking for a large $k$]
There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715.

The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be shared across multiple $k$.



An overly crude approximation of the probability that $q=2^k\,p+1$ is prime is that probability for an integer of same magnitude divisible by neither $2$ nor prime $p$, that is for $p&gt;2$ and by the Prime Number Theorem roughly $\displaystyle\frac{2-2/p}{\ln(q)}$, which we can approximate as $\displaystyle\frac2{\ln(p)+k\ln(2)}$ for our large $p$. A numerical experiment shows that's in the right ballpark, but sizably too high.

A better analysis is that for random large prime $p$, and a small prime $r&gt;2$, the quantity $p\bmod r$ is about uniformly distributed on $[1,r)$, thus $2^k\,p\bmod r$ also is, thus $q=2^k\,p+1$ is divisible by $r$ with probability $1/(r-1)$, rather than $1/r$ for a random integer. It thus contributes to reducing the probability to be prime by a factor $\frac{r-2}{r-1}$ rather than $\frac{r-1}r$. We can correct for that effect, yielding
$$\begin{align}
\Pr(2^k\,p+1\text{ is prime})&amp;\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2&lt;r&lt;\sqrt p}\frac{r\,(r-2)}{(r-1)^2}\\
&amp;\approx\frac{2\,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots
\end{align}$$
since the product quickly converges to the twin prime constant $C_2$ (see A005597). That improved approximation is excellent for large $p$ as in the question.



We move to estimating the probability to find a prime $2^k\,p+1$ for a given $p$ and $k\in[k_0,k_1]$ with $k_0$ and $k_1$ close and commensurate with $\log_2(p)$.

As a crude approximation we can pretend that the probabilities to get a prime for one $k$ are independent of $k$, and approximate the probability that there is one prime $2^k\,p+1$ for $k\in[k_0,k_1]$ as the easily computed
$$1-\prod_{k=k_0}^{k_1}\left(1-\frac{2\,C_2}{\ln(p)+k\ln(2)}\right)$$

For $p\approx 2^{256}$, $k\in[248,264]$ that gives a probability $0.061403\ldots$, meaning we'd need to test about one in $16.286\ldots$ primes $p$ to find a suitable one¹.

This approximation could likely be improved by taking into account that the probabilities for $2^k\,p+1$ to be divisible by a small prime $r$ for a given $p$ are strongly dependent on $k$, since $2^k\bmod r$ is a cyclic function of $k$, and worse of period $(r-1)/s$ often with $s\ge2$ (e.g. for $r=7$).



¹ What I got experimentally is close: $\frac{3395526}{208621}=16.27\ldots$ and $\frac{2116707}{130242}=16.25\ldots$ (scanning primes $p$ starting from $\left\lceil\frac7{22}\,\pi\,2^{256}\right\rceil$ and $\left\lceil\frac{113}{355}\,\pi\,2^{256}\right\rceil$ ).