What is the largest possible length of a prime number?

197 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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