# What is the largest possible length of a prime number?

Let $p$ be a prime number ,

set $f(p)=2p+1$ and define $f^n(p)=f\circ f\circ\cdots\circ f(p)$ composition by $f,$ $n$ times.

And define length of $p$, $L(p)$ as maximum of $n$ such that $f^i(p)$ is prime for all $0\leq i< n$.

For example, $L(3)=2$ since we have chain $3-7$ and $L(2)=5$ as $2-5-11-23-47$.

My question what is the largest possible length for all prime ?

i.e if $M=\sup \{L(p):p\ \text{is prime number} \}$, what is $M$?

• That max should be a sup, as it could be infinite. You might want to try using the heuristic density of Sophie Germain primes to give a heuristic for the probability that a given prime has length $\geq n$. (Remark that $L(p)\geq 1$ if and only if $p$ is a Sophie Germain prime.) That might tell you whether to expect $M<\infty$ or $M=\infty$. – Bruno Joyal May 21 '14 at 22:18
• Examine Cunningham Chains of the first kind. – Peter Woolfitt May 21 '14 at 22:22
• @Peter: Spot on! :) – Bruno Joyal May 21 '14 at 22:35
• As far as I can tell that should be an answer. – user98602 May 22 '14 at 1:20

As Bruno points out, there is no way to settle this question with current knowledge.

However, there is a small note: let your first prime be called $p.$ There are many odd primes $q$ for which $2$ is a primitive root and for which $$p \neq -1 \pmod q.$$ Your function then has $$L(p) \leq 2q - 3$$ for any such $q.$ Furthermore, if $q$ is not one of the $f^n(p),$ then $$L(p) \leq q - 2.$$ This applies to the smallest possible $q$ you can find, so there is an upper bound for any given $p.$

For example, $2 \neq -1 \pmod 5,$ so $L(2) \leq 7.$

When $q$ has 2 as a primitive root, then your sequence, taken $\pmod q,$ has the fixed point $-1 \pmod q,$ and everything else shows up in a long sequence of $q-1$ distinct values, including $0 \pmod q.$ If the prime $q$ is not part of the sequence, a number congruent to $0 \pmod q$ is composite. If the prime $q$ is part of the sequence, the first occurrence is allowed to be $q$ itself, but any other occurrence is a composite number.

Hmmm. In particular, if 2 is a primitive root $\pmod p$ it self, then $L(p) \leq p-1.$ We get this because $p$ occurs in the very first position.

The primes up to 1000 for which 2 is a primitive root are $$3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197,$$ $$211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523,$$ $$541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827,$$ $$829, 853, 859, 877, 883, 907, 941, 947,$$

Evidently much easier to show a chain is short than to find a long one, as the current world record is length 14. See http://oeis.org/A005602

• Thanks for your extended search. – mesel May 22 '14 at 14:31