Assuming $p_i$ is a prime consider the sequence defined by $q_1=p_i$ and $q_n=2\ q_{n-1}+1$ for $n>1$. Let $d$ be the greatest value $n$ for which $q_1..q_n$ are all Sophie Germain primes which I refer to as the depth of $p_i$.

With this definition all non-Sophie Germain primes have depth $d=0$, and all Sophie Germain primes have depth $d\ge 1$.

The following table lists the first Sophie Germain prime of depth $5\le d\le 9$. This list was generated by searching the first $100,000,000$ primes, so there is no Sophie Germain prime of depth $10$ less than or equal to $p_{100,000,000}=2,038,074,743$.

$\begin{array}{cccc} i & p_i & d & q_1..q_d \\ 1 & 2 & 5 & \{2,5,11,23,47\} \\ 24 & 89 & 6 & \{89,179,359,719,1439,2879\} \\ 87359 & 1122659 & 7 & \{1122659,2245319,4490639,8981279,17962559,35925119,71850239\} \\ 1216984 & 19099919 & 8 & \{19099919,38199839,76399679,152799359,305598719,611197439,1222394879,2444789759\} \\ 4991062 & 85864769 & 9 & \{85864769,171729539,343459079,686918159,1373836319,2747672639,5495345279,10990690559,21981381119\} \\ \end{array}$

Question: Is it known whether there is a maximum value for the depth $d$ of a prime $p_i$ or is this tied to the Sophie Germain prime conjecture?


1 Answer 1


Check this out: https://en.m.wikipedia.org/wiki/Sophie_Germain_prime

What you've described is apparently called a Cunningham chain. It has been conjectured that they can be made arbitrarily long, but it cannot be infinitely long.

In terms of your conjecture, it is conjectured that there exists some prime(s) that have a specified depth $d$, but no prime has an infinite depth.

I think I have a proof that all sequences $x_n$ where $x_n= ax_{n-1} +b$ can't be prime for all $n$, but I'll have to do it later.

Not sure if you've found a proof for the result above (or care still), but I found where I had proven it before. Since it's kinda long, I'll paraphrase it a bit, although if you need clarification feel free to comment.

Denote $(a,b)$ by the greatest common divisor between $a$ and $b$. For example, $(45, 30) = 15$. In particular, if $(a,b) = 1$, we say that $a$ and $b$ are relatively prime.

Start by writing $x_n = x_0 + b(n-1)$ for $a = 1$ and

$$x_n = a^nx_0 + b\left(\frac{a^n-1}{a-1}\right)$$

for $a >1$.

Note that $x_n$ is always divisible by $(a,b)$ and $(b,x_0)$. Hence, we will assume $(a,b) = (b,x_0) = 1$.

Showing the statement for $a=1$ is simple by considering $x_{n+1}$ modulo $k$ where $(k,b) = (k,x_0) = 1$. It then follows that

$$n \equiv -x_0b^{-1} \pmod{k}$$

makes $x_{n+1}$ divisible by $k$.

Now, for $a > 1$, take some $k$ so that $k$ is relatively prime to $a,b,x_0$ and define a function $n(t)$ over positive integers $t$ by

$$n(t) = t\phi(k) + 1,$$

where $\phi$ is the Euler-totient function.

Consider $x_{n(t)}$ modulo $k$,

$$x_{n(t)} = a^{t\phi(k) + 1}x_0 + b\frac{a^{t\phi(k) + 1}-1}{a-1} \equiv ax_0 + b \pmod{k},$$

where we used the Euler-Fermat theorem. Since $(a,b) = (b,x_0) = 1$, $ax_0 + b = x_1$ is relatively prime to each of $a,b,x_0$.

Thus, $k = x_1$ satisfies the conditions of $k$ specified, so taking $k = x_1$ implies that each member of the sequence $\{x_{n(t)}\}$ is divisible by $x_1$. But, $\{x_{n(t)}\}$ is strictly increasing, so only $x_{n(1)}$ can possibly be prime.

Therefore, for $t > 1$, $x_{n(t)}$ is composite.


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.