Consider the function $f$ on the prime numbers defined by $$ f(p):= \text{ the greatest prime factor of } 2p+1.$$ The iteration of $f$ from any prime $p<10^8$ converges to the cycle $$(3,7,5,11,23,47,19,13)$$

**Question**: Is it true for any prime $p$?

Let $\ell(p)$ be the number of iterations needed to join the cycle from $p$. The prime number $p$ will be called *champion* if for any prime $q<p$ we have $\ell(q)<\ell(p)$. There are $18$ champions $p<10^8$, computed below with $\ell(p)$. It follows that for any $p < 10^8$ we have $\ell(p) < 2 \ln(p)$ for $p \neq 89$, whereas $\ell(89) \simeq 2.0051\ln(89)$.

```
gap> p:=1;; bb:=0;; while p<100000000 do p:=NextPrimeInt(p); a:=p; b:=0; while a<>3 and a<>7 and a<>5 and a<>11 and a<>23 and a<>47 and a<>19 and a<>13 do b:=b+1; L:=PrimeDivisors(2*a+1); l:=Length(L); a:=L[l]; od; if b>bb then Print([p,b]); bb:=b; fi; od;
[ 2, 1 ][ 29, 3 ][ 41, 4 ][ 53, 6 ][ 79, 7 ][ 89, 9 ][ 311, 10 ][ 1223, 11 ][ 1889, 12 ][ 2833, 13 ][ 3821, 14 ][ 18149, 16 ][ 63521, 17 ][ 222323, 18 ][ 779111, 19 ][ 2167289, 20 ][ 7585511, 21 ][ 19487999, 23 ]
```

We can compute a prime $p$ such that $\ell(p) = r$ (see below for $r=30$).

```
gap> p:=17;; r:=30;; while r>0 do q:=3;; while not IsPrime((q*p-1)/2) do q:=NextPrimeInt(q); od; r:=r-1; Print([q,p]); p:=(q*p-1)/2; od;
[ 7, 17 ][ 13, 59 ][ 61, 383 ][ 7, 11681 ][ 13, 40883 ][ 373, 265739 ][ 61, 49560323 ][ 13, 1511589851 ][ 157, 9825334031 ][ 199, 771288721433 ][ 13, 76743227782583 ][ 31, 498830980586789 ][ 1423, 7731880199095229 ][ 163, 5501232761656255433 ][ 823, 448350470074984817789 ][ 79, 184496218435856252520173 ][ 1171, 7287600628216321974546833 ][ 1663, 4266890167820656516097170721 ][ 193, 3547919174542875893134797454511 ][ 733, 342374200343387523687507954360311 ][ 1627, 125480144425851527431471665273053981 ][ 61, 102078097490430217565502199699629413543 ][ 127, 3113381973458121635747817090838697113061 ][ 163, 197699755314590723869986385268257266679373 ][ 277, 16112530058139143995403890399362967234368899 ][ 2437, 2231585413052271443363438820311770961960092511 ][ 2731, 2719186825804192753738350202549892917148372724653 ][ 193, 3713049610635625205229717201581878778366102955513671 ][ 1453, 358309287426337832304667709952651302112328935207069251 ][ 1609, 260311697315234435169341091280601170984606971427935810851 ]
```

We can generalize the problem to any function $f_k$, where $kp+1$ replaces $2p+1$ above.

For $k=3$, it is the cycle $(2,7,11,17,13,5)$.

For $k=4$, it is $(5,7,29,13,53,71,19,11)$.

For $k=5$, it is $(2,11,7,3)$.

For $k=6$, there are two cycles:$(47,283,1699,2039,2447,14683,8009,1373,107,643,227)$ and
$(13,19,23,139,167,59,71,61,367,2203,13219,547,67,31,17,103,619,743)$.

For $k=7$, it is $(3,11,13,23)$.

For $k=8$, it is $(11,89,31,83,19, 17,137,1097,131,1049,109,97,37)$.

For $k=9$, two cycles: $(13,59,19,43,97,23)$ and $(37,167,47,53,239,269,173,41)$.

Everything is checked for $p<10^6$.

*Bonus question 1*: Does the iteration of $f_k$ converges to finitely many possible cycles, for any $k \ge 2$?

We can generalize the problem to any polynomial function $f \in \mathbb{N}[X]$ splitting on $\mathbb{Q}$ with $f(0)=1$.

For $f(p)=(p+1)(2p+1)$, it is the cycle $(5,11,23,47,19,13,7)$.

For $f(p)=(2p+1)(3p+1)$, it is the cycle $(31,563,23,47,71,107,43,29,59,89,179,359,719,1439,2879,617,463,139)$.

For $f(p)=(3p+1)(4p+1)(5p+1)$, it is the cycle $( 71, 107, 67, 269, 673, 2693, 6733, 1171, 937, 163, 653)$

Everything is checked for $p<10^6$.

*Bonus question 2*: Can we extend to that case?

It seems that it can't be extended to the non splitting case.

For $f(p)=p^2+1$ and from $p=2$, we get the (probable) sequence:

```
2, 5, 13, 17, 29, 421, 401, 53, 281, 3037, 70949, 1713329, 1467748131121, 37142837524296348426149, 101591133424866642486477019709, 1650979973845742266714536305651329, 78343914631785958284737, 4029445531112797145738746391569, 350080544438648120162733678636001, 26208090024628793745288451837610346882122253572537, ...
```

For $f(p)=p^2+3p+1$ and from $p=2$, we get the (probable) sequence:

```
2, 11, 31, 211, 821, 135301, 3809941, 742299251, 2894402701, 11096115237403051, 13495491562451, 5906592644484061, 3006276317783130610918295261, 680868245636686686301066879953955425558991, 859331554798594732550606265780004082746150814706504421, 13431381921273506538508334090334652350875716299550588398947479075941548746770801901,...
```

*Bonus question 3*: Is it true that for any polynomial function $f \in \mathbb{N}[X]$ with $f(0)=1$ and without rational root, a sequence starting from any prime number $p$ never reach a cycle?

Note that we have seen a class of polynomials for which we expect the convergence to finitely many possible cycles, and a class for which we expect no cycle at all. We are wondering about an intermediate case: Is there a polynomial with a convergence to infinitely many cycles?

on averagelike raising to a 0.624... power (see Golomb-Dickman constant) which overpowers affine transformations, and is overpowered by polynomial ones of degree is $\ge 2$. Unlike in the Collatz problem, the steps up and down are drastic and of different nature (polynomial vs. arithmetic) so once both occur I'd expect things to "mix up" and follow long term expectations. A very very faint hope (in degree $\ge 2$) would be if after 1 or 2 steps up from a small prime, one hit a product of small primes... $\endgroup$ – Yaakov Baruch Jul 14 '17 at 8:48