32

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?

Sebastien Palcoux
  • 25,922
  • 5
    By searching the sequence $3,7,5,11,23,47,19,13$ on oeis, we find A287865 (posted on Jun 04 2017). It refers to Oskars Rieksts. He seems to know this problem since July 2016 (see here). I don't know if this problem was known to someone before him. – Sebastien Palcoux Jul 11 '17 at 00:43
  • While not quite the same thing, you could construct some small cycles and then fit a polynomial map to them. For infinitely many cycles, consider floor or ceiling of p to a power ($e/2$ perhaps?) matching the down scaling of gpf. Gerhard "Make Up Your Own Answer" Paseman, 2017.07.11. – Gerhard Paseman Jul 11 '17 at 17:05
  • 2
    It would be surprising to find that intermediate case. The step down in the iteration is on average like 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... – Yaakov Baruch Jul 14 '17 at 08:48
  • @YaakovBaruch: so a nice function to study iterations would be $f(p)= \text{gpf}(\left \lfloor{p^{\alpha}}\right \rfloor)$ or $\text{gpf}(\left \lceil{p^{\alpha}}\right \rceil)$ with $\alpha = \lambda^{-1} \simeq 1.6017170700590876997$ the inverse of the Golomb–Dickman constant. Note that $(10^{r})^{1+10^{-n}} \sim 10^{r} + r \ln(10) \cdot 10^{-n+r}$ for $r \ll 10^n$, so the above approximation of $\alpha$ would be ok if we deal with primes $p<10^{10}$. – Sebastien Palcoux Jul 14 '17 at 12:39
  • @SebastienPalcoux. In Collatz's problem the components of the $\mathbb N \rightarrow \mathbb N$ iterative step are simple, closely related, with clear pressure in one direction (down) and yet the tantalizing early major anomaly of 27. If not done before, it could be an excellent question for MathOverflow to ask for examples of similarly intriguing functions $\mathbb N \rightarrow \mathbb N$ - but personally I think that the one you are proposing is too contrived. Cheers – Yaakov Baruch Jul 14 '17 at 12:48
  • Obviously, we get infinitely many cycles with the function $f(p)=p^2$. – Sebastien Palcoux Jul 14 '17 at 14:32
  • @YaakovBaruch: it's interesting to note that if we take $f(p)$ to be the largest prime factor of $p^2 + 1$ then iteration appears to lead to sequences that head off to infinity, as you'd expect since the Golomb-Dickman constant is greater than $1/2$. – Michael Lugo Jul 15 '17 at 15:07
  • The last four digits of $\alpha=\lambda^{-1}$ (written in a previous comment) are wrong, it is not $6997$ but $5533$. – Sebastien Palcoux Jul 18 '17 at 18:25
  • 1
    The sequence for $p^2+1$ was posted to OEIS in 2006, http://oeis.org/A031439 – Gerry Myerson Oct 22 '17 at 08:29

2 Answers2

6

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.

Gerhard Paseman
  • 12,968
  • 4
    Evidentally the map sending $p$ to $2p+1$ generates $17$ primes in a row if started at $p_1=2759832934171386593519.$ I didn't check but one might imagine that at the $18$th iteration the composition result (over $250000p_1$ has largest prime factor quite large and the start of another long chain. So even if there was s bound on how long it would take to get to a composite , it wouldn't rule out growth without bound. And the expected result is that there are arbitrarily long increasing chains. But I do agree that one would anticipate that everything does get to that cycle. – Aaron Meyerowitz Jul 11 '17 at 06:32
  • 1
    Hmm. I was pretty sure each affine map had a prime p in which the map not only had a finite period mod p but also had orbit through 0. Thanks for checking. I will sleep on this and hope for a better resolution. Gerhard "Maybe I Need More Citations" Paseman, 2017.07.10. – Gerhard Paseman Jul 11 '17 at 06:42
  • 1
    @AaronMeyerowitz: alas, the 18th term is 361736822347711983585853439 with largest factor 55442017698213695587 and from there things quickly collapse into the known cycle. (This is not surprising as the larger the number the more likely it is to have factors, and even many large factors.) – Yaakov Baruch Jul 11 '17 at 13:05
  • 1
    For large numbers the expected drop at each down step is about 37% logarithmically, see Golomb-Dickman constant (this is not affected by the zero probability case of the number being prime and the drop being replaced by a logarithmically insignificant constant factor increase). So it's hard to imagine a path to infinity. – Yaakov Baruch Jul 11 '17 at 13:25
  • Easiest to imagine: it never happens but we will never see a proof. Much harder: a proof will be found. Hardest: an unbounded chain. – Aaron Meyerowitz Jul 11 '17 at 14:13
  • @GerhardPaseman: you are correct about orbiting through 0. If $p$ is the starting prime (and $p$ doesn't divide the parameters of the affine transformation) then (Mod $p$) it will cycle trough 0 within $p-1$ steps. (A leisurely 2759832934171386593518 steps in the above example...) – Yaakov Baruch Jul 11 '17 at 15:38
  • 2
    An additional bit of information can be found at keyword "Cunningham chain" ? https://en.wikipedia.org/wiki/Cunningham_chain There is also Aaron's number $p_1=2759...19$ mentioned as record holder found in 2008 – Gottfried Helms Jul 25 '17 at 19:47
4

On bonus question 3, for $f_k(p)=kp^2+1$, I have found several values for $k$ which have a 2-cycle. I can't show that all $p$ will fall into these cycles or that these are the only cycles. Working backwards from these cycles, we can find which numbers do fall into them.

Edit update: In addition to the examples below, I google searched looking for other information, and here someone found for $k=1$ we have a 5-cycle $(19121, 10753313, 1241761, 3817193, 107837)$. This confirms part of my speculation that my computer search was limited to the computational low-hanging fruit. /Edit

For $k=1$ we have a cycle $(89,233)$; $k=5$ has cycle $(43,67$); $k=11$ has cycle $(23,97)$; $k=23$ has cycle $(3,13)$; $k=41$ has cycle $(67,409)$; $k=71$ has cycle $(5,37)$; $k=85$ has cycle $(383,769)$; $k=113$ has cycle $(509,1021)$; $k=143$ has cycle $(7,73)$; $k=215$ has cycle $(257, 467)$; $k=311$ has cycle $(67,277)$; $k=359$ has cycle $(11,181)$; $k=863$ has cycle $(17,433)$; $k=951$ has cycle $(67,73)$; $k=1238$ has cycle $(13,41$); $k=1427$ has cycle $(167,293)$; $k=1808$ has cycle $(107,271)$; $k=1811$ has cycle $(17,61)$; $2089$ has cycle $(31,241)$; $k=2501$ has cycle $(167,251)$; $k=4199$ has cycle $(59,101)$; $k=5903$ has cycle $(61,151)$; $k=6119$ has cycle $(61,179)$; $k=6269$ has cycle $(29,67)$; $k=7679$ has cycle $(109,151)$; $k=9407$ has cycle $(7,97)$.

I found one 3-cycle at $k=7$ which goes $(79,127,1283)$.

As well, for $g_k(p)=kp^2-1$, aside from perfect square $k's$, I found $k=11$ has cycle $(239,3307)$; $k=19$ has cycle $(157,233)$; $k=23$ has cycle $(929,2711)$; $k=61$ has cycle $(127,503)$; $k=103$ has cycle $(857,1283)$; $k=1639$ has cycle $(127,197)$.

$k=123$ has a 3-cycle $(443,449,823)$; $k=409$ also has a 3-cycle $(71,317,137)$.

At first glance I notice how many of the $k's$ are prime, but not all. Now, why so many 2-cycles? I think it is because of my computational limitations since the numbers get large quickly. I found these using unsigned long integer data type; I predict arbitrary precision calculations would uncover larger cycles.

For $k=23$, we have $23*3^2+1=2^4*13$, and $23*13^2+1=2^4*3^5$, and you can see that these large numbers must be very composite to have such low greatest prime factors. Another pleasing example is $k=143$; $143*73^2+1=2^6*3^5*7^2$. That explains why these are so rare.

Shawn Schafer
  • 41