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$:
- Is $\lambda(p)<\infty$ for all primes $p$?
- Is $\lambda$ bounded?
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$.