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?
Best Answer
Short (non-) answer: I don't know.
Long (too long for a comment, so also a non-) answer: Because of how this dynamic is composed of two others, namely affine (x goes to b+ax) and divisor (greatest prime, to be precise), I am guessing the answer is yes. This is because the down step scaling appears larger than the up step scaling (citation needed).
Note that repeated applications of (b+ax) yield for initial integer x either a fixed point or a composite integer. Further, there is a constant upper bound on the number of iterations needed to reach this composite, and my guess is that the expected ratio of composite/gpf(composite) is not bounded. In the Collatz dynamic, I suspect the ratio of up to expected down scaling is not small enough to resolve the problem (citation really needed), whereas in this problem I think it can help resolve the situation.
Update 2017.07.11: First, thanks to Aaron Meyerowitz for calling me out on an unsupported statement (constant number of iterations), and for supporting (but not proving) my contention above that the answer is yes.
Second, thanks to Yaakov Baruch for providing more support for a yes answer. Finally, thanks to Sebastian Palcoux for providing some more examples on which to ponder.
The additional comments and posting suggest that my main guess above holds, namely that gpf scales downward more than affine maps scale upward. However, Aaron's comment indicates that more is going on with affine maps than I originally claimed. To illustrate, I work with the first map $f$ sending x to 2x+1.
Consider a version of $f$ modulo a large prime $p$, and look at the orbit of 0 under $f$ modulo $p$. The size of the orbit corresponds to the multiplicative period of 2 modulo $p$. When 2 is a primitive root mod $p$, there is only one modulo class that stays outside the orbit of 0, namely $p-1$.
This means that if $f$ iterated k times with an initial prime value $q$ produces k more primes, then all these primes must be 1 less than those primes less than k+1 for which 2 is a primitive root. For Aaron's example of k=17, the primes are all -1 mod (3*5*11*13). Not only that, the primes lie outside a subset of residue classes for a product other primes (7*17*19*23*...) as well.
So the claim of a constant upper bound on the number of iterations is incorrect. However, the initial primes which make it past k, a small number of iterations gets fewer and fewer, and for each smaller prime $p$ has to avoid a certain k many residue classes for that $p$ for $f$ to produce k primes starting from $q$. Based on the numerical data for the affine maps and the effective divisor max among a finite set of maps, constant iterations becomes something like log $q$ many iterations (yet another citation needed) to avoid a composite number. Meanwhile, gpf scaling downward still seems to outweigh scaling upward. Again, not quite an answer.
End Update 2017.07.11
Gerhard "Not Arithmetic Dynamicist Yet (Self-citation)" Paseman, 2017.07.10.