# If $p$ is prime, does there exist a positive integer $k$ such that $2^k\,p+1$ is also prime?

A prime $p$ such that $2\,p+1$ is also prime is called a Sophie Germain prime. It is conjectured that there are infinitely many such primes. This prompted me to ask the following question: given a prime $p$, is there a positive integer $k$ such that $2^k\, p+1$ is prime? Define $\lambda(p)$ to be the smallest such $k$ if it exists, $\infty$ otherwise. If $p$ is a Sophie Germain prime, then $\lambda(p)=1$. The function $\lambda$ doesn't seem to have any regularity, other than the following: $\lambda(p)$ is even if and only if $p\equiv1\mod3$. The values for the first 100 primes:

1, 1, 1, 2, 1, 2, 3, 6, 1, 1, 8, 2, 1, 2, 583, 1, 5, 4, 2, 3, 2, 2,
1, 1, 2, 3, 16, 3, 6, 1, 2, 1, 3, 2, 3, 4, 8, 2, 7, 1, 1, 4, 1, 2,
15, 2, 20, 8, 11, 6, 1, 1, 36, 1, 279, 29, 3, 4, 2, 1, 30, 1, 2, 9,
4, 7, 4, 4, 3, 10, 21, 1, 12, 2, 14, 6393, 11, 4, 3, 2, 1, 4, 1, 2,
6, 1, 3, 8, 5, 6, 19, 3, 2, 1, 2, 5, 1, 5, 4, 8


Some extreme values: $\lambda(2\,897)=9\,715$, $\lambda(3\,061)=33\,288$. There are several questions that can be asked about $\lambda$:

1. Is $\lambda(p)<\infty$ for all primes $p$?
2. Is $\lambda$ bounded?
3. Can something be said about the asymptotic behavior as $N\to\infty$ of the average $$\Lambda(N)= \frac{1}{N}\sum_{n=1}^N\lambda(p_n),\quad N\in\mathbb{N},$$ where $p_n$ is the $n$-th prime? Here is a graph of $\Lambda(N)$ for $1\le N\le700$.

Actually $\lambda$ might not be finite, for example $271129$ is prime and $271129 \cdot 2^k+1$ is never prime. This is a special case of a Sierpinski number. Every number in the set $\{271129 \cdot 2^k+1\}$ is divisible by a number in the set $\{3, 5, 7, 13, 17, 241\}$.
• See also the "seventeen or bust" project, seventeenorbust.com and more closely related to the question at hand, prothsearch.net/sierp.html, according to which 271129, found by Nathan Mendelsohn in 1976, is the smallest known prime Sierpinski number, with 11 smaller candidates not yet ruled out. In particular, $p=10223$ is still in the running. – Gerry Myerson Jun 4 '12 at 1:13
• Update: on 31 Oct 2016, Péter Szabolcs found that 10223 is not Sierpinski: $2^{31172165}10223+1$ is prime. epcc.ed.ac.uk/blog/2016/11/07/… newscientist.com/article/… – Rosie F Jun 2 '18 at 17:51