18
$\begingroup$

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

    enter image description here

1 Answers 1

20

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\}$.

  • 0
    Update: on 31 Oct 2016, Péter Szabolcs found that 10223 is not Sierpinski: $2^{31172165}10223+1$ is prime. https://www.epcc.ed.ac.uk/blog/2016/11/07/how-do-you-solve-problem-sierpinski https://www.newscientist.com/article/2113283-crowdsourced-prime-number-could-help-solve-a-50-year-old-problem/2018-06-02