A Collatz-like function that bifurcates on primes

Question

This is likely piling one mystery on another, but ...

I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows: $$ f(n) = \begin{cases} n^2 & \text{if} \;n \;\text{is prime} \\ \lfloor n/2 \rfloor & \text{if} \;n \;\text{is composite} \end{cases} $$ For example, $$ \begin{eqnarray*} f(11) &=& 121 \\ f(121) &=& 60 \\ f(60) &=& 30 \\ f(30) &=& 15 \\ f(15) &=& 7 \\ f(7) &=& 49 \\ f(49) &=& 24 \\ f(24) &=& 12 \\ f(12) &=& 6 \\ f(6) &=& 3 \\ f(3) &=& 9 \\ f(9) &=& 4 \\ f(4) &=& 2 \\ \end{eqnarray*} $$ and now we are in a $2/4$ cycle.

For all $n=2,\ldots,228$, repeated applications of $f(n)$ leads to a $2/4$ cycle. For $n=229$ (a prime), $f(229)$ seems to shoot off, in spurts, to large values: $$229, 52441, 26220, 13110, 6555, 3277, 1638, 819, 409, 167281, 83640, 41820, 20910, 10455, 5227, 27321529, \ldots $$

---

     
     

---

For $n=2,\ldots,10^4$, about $87$% end in a $2/4$ cycle, and $13$% seem to shoot off into the realm of large numbers.

Q0. Have iterates of this function $f(n)$ (or its close analogs) been studied before?

Q1. Is there any hope of explaining the behavior of iterates of $f(n)$?

Q2. Can the convergence of iterates of $f(n)$ be proved for selected classes of values of $n$?

For example, $n=2^k$ always ends in the $2/4$ cycle.

Q3. For which values of $n$ can it be proved that $f^k(n) \to \infty$?

---

(Added 8Aug15): Here are the trajectories of the first 20 primes (in red), all heading toward the $2/4$ cycle (green). It remains unsettled if (a) any integer starting value diverges to $\infty$, and (b) whether the only cycle is the $2/4$ cycle.

---

     

---

Answer 1

Let us use a rough estimate for the probability of a large integer $n$ being prime as $\frac{1}{\ln n}$ (as suggested by PNT). Then the expectation of $\ln f(n)$ can be estimated as $$\frac{1}{\ln n}\cdot \ln n^2 + \left(1-\frac{1}{\ln n}\right)\cdot \ln \lfloor \frac{n}{2}\rfloor = \ln n + 1 - \ln 2 + O(\frac{1}{\ln n}).$$ Since $1-\ln 2>0$, we have that the expectation of $\ln f(n)$ is larger than $\ln n$, which suggests that iterations of $f()$ may diverge for some large $n$.

This approach also suggests that to eliminate divergence, instead of the divisor 2 in the composite case one needs to take a divisor larger than $e\approx 2.718$ (e.g., 3).

P.S. Unavoidable divisions after squaring do not change the picture. E.g., if we have $\lfloor\frac{n^2}{2^5}\rfloor$ instead of $n^2$, the expectation of $\ln f(n)$ is still estimated as $\ln n + 1 - \ln 2 + O(\frac{1}{\ln n})$ for large $n$.

Answer 2

Max Alekseyev's answer suggests that many orbits should diverge, since $\operatorname E(\ln f(n))>\ln n$. However, by a more careful accounting of run lengths, I find that every orbit should almost surely return to its starting point, assuming a random distribution of primes such that any number $n$ has an independent $\frac1{\ln n}$ probability of being prime.

First, let's consider runs of composite numbers. Starting at a composite number $n_0$, we repeatedly apply the halving rule $\lfloor\frac n2\rfloor$ until we reach a prime number $N$, at which point we apply the squaring rule $n^2$ to obtain the starting point of the next run. We will consider $N$ as a random variable in terms of $n_0$.

Assuming our $\frac1{\ln n}$ distribution of primes, we see that after $t$ steps, a run has probability $(1-\frac1{\ln(n_0/2^0)})(1-\frac1{\ln(n_0/2^1)})\cdots(1-\frac1{\ln(n_0/2^{t-1})})$ to have never reached a prime. To estimate the logarithm of this, we set up an integral in terms of $t$, and extract the leading terms: $$\begin{split}I(t)&=\int\ln\left(1-\frac1{\ln2^t}\right)\,dt\\&=t\ln\left(1-\frac1{t\ln2}\right)-\log_2(t\ln2-1)\\&=-\log_2t-\frac{\ln\ln2+1}{\ln2}+O(t^{-1})\text{ as }t\to\infty.\end{split}$$

Now, taking $x_0=\ln\ln n_0$ and $X=\ln\ln N$, our integral runs from $t=\frac{e^X}{\ln2}$ to $t=\frac{e^{x_0}}{\ln2}$, yielding the log-probability we're looking for. Thus, we obtain an approximate CDF for the distribution of $X$ given $x_0$: $$\begin{split}F(x)&=e^{I(e^{x_0}/\ln2)-I(e^x/\ln2)}\\&\approx e^{-\log_2(e^{x_0}/\ln2)+\log_2(e^x/\ln2)}\\&=e^{(x-x_0)/\ln2}.\end{split}$$

Beware that the exact version doesn't quite work as a CDF on $[0,x_0]$, since it doesn't go down to $0$, so the PDF should be scaled as $\frac{F'(x)}{1-F(0)}$ when we work with it. But the approximate version, supported on $(-\infty,x_0]$, has no such scaling issue. So we can continue to find the expected value and variance of $X$: $$\begin{split}\operatorname E(X)&=\frac1{1-F(0)}\int_0^{x_0}xF'(x)\,dx\\&\approx\frac1{\ln2}\int_{-\infty}^{x_0}xe^{(x-x_0)/\ln2}\,dx\\&=x_0-\ln2;\\\operatorname{Var}(X)&=-\operatorname E(x)^2+\frac1{1-F(0)}\int_0^{x_0}x^2F'(x)\,dx\\&\approx-(x_0-\ln2)^2+\frac1{\ln2}\int_{-\infty}^{x_0}x^2e^{(x-x_0)/\ln2}\,dx\\&=(\ln2)^2.\end{split}$$

So we can see that as $x_0\to\infty$, the expected end point $X$ approaches $x_0-\ln2$. Furthermore, since $\ln\ln N^2=X+\ln2$, the expected start point of the following run approaches $x_0$ exactly. In other words, the successive runs can be modeled as an unbiased random walk in $x$-space, which almost surely returns to the starting point in finite time.

However, we aren't quite done yet, since our approximation has produced an underestimate for $\operatorname E(X)$. Numerically integrating the exact $\operatorname E(X)$, we find that the residual $\operatorname E(X)-(x_0-\ln2)$ is positive for all $x_0$:

So the random walk is somewhat biased away from the origin. But not by much: the residual approaches $\frac{\ln2}{2(1-\ln2)}e^{-x_0}\approx1.1295e^{-x_0}$, and never exceeds $1.1544e^{-x_0}$. Is this exponentially-decaying bias enough to make the random walk diverge? I'm not an expert on Markov processes, but I ran some Monte Carlo simulations for a random walk with Gaussian steps $s_x\sim\mathcal N(\mu=1.1295e^{-x},\sigma^2=(\ln2)^2)$. Let $\tau$ denote the number of steps taken to hit the origin, from some positive starting point. For an unbiased random walk, we have $\mathbb P(\tau>t)\sim\frac C{\sqrt t}$ as $t\to\infty$ for some $C$, i.e., the hitting times approach a power-law distribution. And my simulations indicate that the same distribution empirically holds for this slightly-biased walk. For instance, the probability tends steadily toward $0$ on this log–log plot even with a relatively large starting point:

Therefore, the bias seems insufficient to make the walk diverge with probability $>0$, and there should still almost surely be no divergent orbits as a result.

---

How well does this model match the actual run lengths? I split the range $x_0\in[0,6]$ into intervals of length $2^{-8}$. Then, for each interval, I generated a sample of $2^{16}$ different $n_0$ values, and measured the expectation and variance of $X-(x_0-\ln2)$ within the sample. These are the simulation results, compared to the theoretical prediction:

The simulated variance tracks the theoretical variance pretty well. Meanwhile, the simulated residuals are persistently higher than the theoretical result. But at least they appear to track it to within a constant factor (before they start fraying apart due to the limited sample size), as seen in the log scale on the right. So while I'm not sure what effect could be causing this gap, it's not enough to defeat the basic non-divergence result.

So how many steps might an orbit take before returning? As it turns out, once a value departs far enough from the origin, it can take an exceptionally long time to return. Take the orbit $(f^n(397))_{n\geq0}$, which is the first not known to reach $2$ using a probabilistic primality test. I've simulated it for a fairly long distance (A376801), and it goes up and down quite drastically: it ascends up to $f^{426080}(397)\approx9.99983\cdot10^{25493}$, then goes all the way back down to $f^{613572}(397)=8111$ before flying off even further. Running some more Monte Carlo simulations from $f^{2307823}(397)\approx1.44443\cdot10^{400228}$, I find that the median number of steps to reach the origin (i.e., a value $\leq397$) is about $3.8\cdot10^{12}$, the 90th percentile is about $2.2\cdot10^{60}$, and the 99th percentile is on the order of $10^{605}$. So it's likely very difficult to simulate the orbit in full, even if we know that it should eventually return.

Answer 3

The full detail of this is of course a complex matter but I can build out some structure and connect the problem to some powerful tools for you; namely that, like the Collatz conjecture, this structure descends linear combinations of Lucas sequences.

The floor function of dividing by two descends the sequences $x_{n+1}=2x_n+1$; e.g.:

$0,1,3,7,15,31,63,\ldots$

Which should be fairly obvious. Furthermore if you divide alternate numbers in this sequence by $3$ you have the immediate odd predecessors of $1$ in the Collatz graph; namely $\{1,5,21,85,341,\ldots\}$ so the connection is fairly obvious.

Numbers just below any descending sequence converge to the same path. In fact the catchment gets wider the higher up the sequence you go, so e.g. $\{62,61,60\}$ go to $15$ then $\{62,61,60,59,58,57,56\}$ go to $7$ etc.

Of course your function will descend these sequences and their neighbourhoods until it hits some highest prime so to build the graph it's necessary to break apart the descending sequences at the prime numbers and graph those upwards to $x^2$ instead of down, connecting the next descending sequence.

I happened to choose the Mersenne numbers, and there are likely infinitely many prime examples although like all Lucas sequences of the first kind this is a divisibility sequence and therefore only a number with a prime index can itself be prime. But this isn't generally the case in all of your function's descending sequences.

The Mersenne numbers are the Lucas sequence $U_n(3,2)$. You can generate every such descending sequence which your function descends, by the linear combinations of $U_n(3,2)$ with its companion $V_n(3,2)=2,3,5,9,17,33\ldots$

$U_n$ is the sequence $2^n-1$ while $V_n$ is the sequence $2^n+1$ so they converge in $\Bbb{Z}_2^{\times}$ to $\pm1$ giving you a set dense enough in $\lvert\cdot\rvert_2$ that perhaps intuitively hints at them covering a set $\{z_1,z_2\in\Bbb{N}:\lvert z_1-z_2\rvert_2\leq\frac{1}{2}\}$ i.e. having an integrality gap of 2 - the odd numbers.

To fully index your descending sequences, and graph the vertices where they stop descending and go up, you need to identify the set of linear combinations of these such that the least value in the sequence is a prime number.

To do that, you need the set of primes $p$ such that $2p+1$ is not prime and define the sequence $S_p=a\cdot U_n(3,2)+b\cdot V_n(3,2)$ by setting $b\cdot V_0(3,2)=p$ and choosing $a$ such that $S_{p+1}=2p+1$

That gives you the set of sequences:

$S_p=(\frac{p}{2}+1)\cdot U_n(3,2)+(\frac{p}{2})\cdot V_n(3,2)$

Next you need to build the successor relation between these sequences; i.e. from the prime at the base of one, to the next descending sequence via the function $x^2$. A (fairly obvious) observation is that the floor function of an odd square halved is equal to $\frac{n^2-1}{2}$. All odd squares are of the form $4n+1$ so the function $p^2$ will always be followed by at least a division by $4$, so we will always have: $\dfrac{p^2-1}{4}$ before possibly more divisions by $2$.

The next part of the exercise is to show that the function $x^2$ totally orders these sequences $S_p(3,2)$.

I could go on but you are probably bored (and answering Collatz-related questions can be risky for low-rep users!) Hopefully I have built out a good amount of the structure which others with greater skills than me may be able to take further.

Another critical structural note to bear in mind is that once you have eliminated unnecessary structure such as perhaps the even numbers, the leaves of this graph, if there are any, will initially be among the primes $p$ for which $2p+1$ is also a prime since these $p$ are the primes which cannot be descended to down some sequence $S_n$ (as obviously any such descent would stop at $2p+1$ and ascend, if $2p+1$ were prime). But if I were a betting man I would predict that the "unnecessary structure" is actually pretty complex and there is a vast amount to be whittled away, and that in the final construct of this graph, the Mersenne Primes may actually be the leaves of the graph, and that the proof this converges to a cycle for all inputs is largely equivalent to there being infinitely many Mersenne Primes. But that is conjecture.

There is a vast array of research into Lucas sequences and numerous algebraic structures underpin any set of linear sequences of them as per the link I gave above. The next part of the exercise I would suggest is to take a look at that structure and find how it determines that the function $p\to p^2$ preorders the sequences $S_p=(\frac{p}{2}+1)\cdot U_n(3,2)+(\frac{p}{2})\cdot V_n(3,2)$

Answer 4

This is not an answer, just a comment to give another display of the results for smaller $n$. It is produced using Pari/GP and its inherent "ispseudoprime()" function.
I document the (odd) initial number $n$ and then a string of numbers. Here the numbers mean the number of consecutive division operations after one squaring operation. If $n$ is a (strong pseudo-) prime then the string of numbers begins with a zero, because the number of division-operations is zero before the first squaring operation occurs.

(btw: Pari/GP gives also a finite length for $n=229$; (the same number $6309$ steps as in @Mirko's comment)

3 : 0,2
5 : 0,3,2
7 : 0,4,2
9 : 2
11 : 0,4,4,2
13 : 0,5,3,2
15 : 1,4,2
17 : 0,7
19 : 0,5,4,4,2
21 : 2,3,2
23 : 0,8
25 : 3,2
27 : 1,5,3,2
29 : 0,6,5,3,2
31 : 0,7,4,2
33 : 4
35 : 1,7
37 : 0,8,3,2
39 : 1,5,4,4,2
41 : 0,7,5,3,2
43 : 0,8,4,2
45 : 2,4,4,2
47 : 0,7,7
49 : 4,2
51 : 4,2
53 : 0,6,8,4,2
55 : 2,5,3,2
57 : 3,4,2
59 : 0,8,5,3,2
61 : 0,7,6,5,3,2
63 : 1,7,4,2
65 : 5
67 : 0,8,7
69 : 2,7
71 : 0,5,13,2
73 : 0,6,6,7,7,7,6,5,3,2
75 : 1,8,3,2
77 : 2,5,4,4,2
79 : 0,6,7,6,6,7,7,7,6,5,3,2
81 : 4,3,2
83 : 0,6,7,7,7,6,5,3,2
85 : 4,3,2
87 : 1,8,4,2
89 : 0,7,7,6,5,3,2
91 : 3,4,4,2
93 : 2,8
95 : 1,7,7
97 : 0,7,6,6,7,7,7,6,5,3,2
99 : 5,2
101 : 0,7,6,7,6,6,7,7,7,6,5,3,2
103 : 0,5,11,6,8,4,2
105 : 3,5,3,2
107 : 0,7,7,7,6,5,3,2
109 : 0,9,8
111 : 3,5,3,2
113 : 0,6,5,12,9,10,5,13,2
115 : 4,4,2
117 : 2,6,5,3,2
119 : 1,8,5,3,2
121 : 4,4,2
123 : 1,7,6,5,3,2
125 : 2,7,4,2
127 : 0,9,7,4,2
129 : 6
131 : 0,8,8,7
133 : 6
135 : 1,8,7
137 : 0,6,9,11,5,3,2
139 : 0,9,8,3,2
141 : 3,7
143 : 1,5,13,2
145 : 6
147 : 1,6,6,7,7,7,6,5,3,2
149 : 0,7,6,6,12,17,7,6,5,3,2
151 : 0,8,7,7,6,5,3,2
153 : 3,5,4,4,2
155 : 3,5,4,4,2
157 : 0,13,2
159 : 1,6,7,6,6,7,7,7,6,5,3,2
161 : 5,3,2
163 : 0,8,5,11,6,8,4,2
165 : 2,7,5,3,2
167 : 0,11,5,3,2
169 : 5,3,2
171 : 5,3,2
173 : 0,6,6,12,17,7,6,5,3,2
175 : 2,8,4,2
177 : 4,4,4,2
179 : 0,10,7,4,2
181 : 0,8,9,7,4,2
183 : 4,4,4,2
185 : 3,8
187 : 3,8
189 : 2,7,7
191 : 0,9,5,13,2
193 : 0,14
195 : 1,7,6,6,7,7,7,6,5,3,2
197 : 0,8,8,7,7,6,5,3,2
199 : 0,5,12,9,10,5,13,2
201 : 6,2
203 : 1,7,6,7,6,6,7,7,7,6,5,3,2
205 : 6,2
207 : 1,5,11,6,8,4,2
209 : 4,5,3,2
211 : 0,7,12,6,5,3,2
213 : 2,6,8,4,2
215 : 1,7,7,7,6,5,3,2
217 : 4,5,3,2
219 : 1,9,8
221 : 4,5,3,2
223 : 0,9,7,6,6,7,7,7,6,5,3,2
225 : 5,4,2
227 : 0,14,2
229 : 0,7,5,7,8,25,34,19,26,58,28,8,8,21,10,13,5,21,25,7,32,10,13,6,5,14,18,20,9,27,12,41,33,14,11,52,25,37,52,14,23,141,35,79,78,64,149,23,446,167,341,716,22,165,316,337,152,65,62,1038,179,369,71,287,69,20,6,7,7,7,6,5,3,2
231 : 5,4,2
233 : 0,10,6,8,4,2
235 : 3,6,5,3,2
237 : 2,8,5,3,2
239 : 0,8,9,7,6,6,7,7,7,6,5,3,2
241 : 0,6,6,20,13,2
243 : 5,4,2
245 : 2,7,6,5,3,2
247 : 2,7,6,5,3,2
249 : 3,7,4,2
251 : 0,10,7,6,5,3,2
253 : 3,7,4,2
255 : 1,9,7,4,2
257 : 0,15
259 : 7
261 : 7
263 : 0,5,16,5,13,2
265 : 7
267 : 7
269 : 0,12,7
271 : 0,10,5,13,2
273 : 4,7
275 : 1,6,9,11,5,3,2
277 : 0,7,7,7,20,14,6,9,18,10,21,28,7,23,74,20,56,100,118,214,113,600,16,62,293,58,45,13,9,22,12,5,4,4,2
279 : 1,9,8,3,2
281 : 0,5,8,10,22,25,13,2
283 : 0,12,5,4,4,2
285 : 2,5,13,2
287 : 2,5,13,2
289 : 7
291 : 7
293 : 0,9,11,5,3,2
295 : 2,6,6,7,7,7,6,5,3,2
297 : 3,8,3,2
299 : 1,7,6,6,12,17,7,6,5,3,2

Update
according to the nice pictures of @legionMamma I made one for the n=229 case in logarithmic scale (more informative than that in the thread's question-box)