6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Bruno Joyal May 21 '14 at 22:18
  • 3
    $\begingroup$ Examine Cunningham Chains of the first kind. $\endgroup$ – Peter Woolfitt May 21 '14 at 22:22
  • $\begingroup$ @Peter: Spot on! :) $\endgroup$ – Bruno Joyal May 21 '14 at 22:35
  • $\begingroup$ As far as I can tell that should be an answer. $\endgroup$ – user98602 May 22 '14 at 1:20
1
$\begingroup$

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

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

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.