Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 14 down vote accepted

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

share|improve this answer
4  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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