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

$\endgroup$
20
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 4 '12 at 1:13
  • $\begingroup$ 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/… $\endgroup$ – Rosie F Jun 2 '18 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.