Return to Question

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 ]

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

gap> p:=1; while p<1000000 do p:=NextPrimeInt(p); a:=p; while a<>3 do L:=PrimeDivisors(2*a+1); l:=Length(L); a:=L[l]; od; od; true;

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

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 ]

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

gap> p:=1; while p<1000000 do p:=NextPrimeInt(p); a:=p; while a<>3 do L:=PrimeDivisors(2*a+1); l:=Length(L); a:=L[l]; od; od; true;

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

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: does the iteration of $f_k$ converges to finitely many possible cycles, for any $k \ge 2$?

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

gap> p:=1; while p<1000000 do p:=NextPrimeInt(p); a:=p; while a<>3 do L:=PrimeDivisors(2*a+1); l:=Length(L); a:=L[l]; od; od; true;

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

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?