# Borderline Collatz-like problems

The usual Collatz map is $$C:n \mapsto n/2$$ if $$n$$ even, $$(3n+1)/2$$ if $$n$$ odd. Let $$f^{\circ (r+1)}:=f \circ f^{\circ r}$$.

We suspect that for every fixed $$n>0$$, the sequence $$C^{\circ r}(n)$$ never diverges to infinity (and more strongly, always converges to $$1$$), because (together with experimental checking) heuristically the application of $$C$$ to a random number multiplies it in geometric average by $$(\frac{1}{2} \cdot \frac{3}{2})^{1/2} = \frac{\sqrt{3}}{2} < 1$$.

The (borderline) Collatz-like problems:

A map $$f: \mathbb{N} \to \mathbb{N}$$ will be called a Collatz-like map if $$0 \neq \lim_{n \to \infty} \left( \prod_{r=1}^n \frac{f(r)}{r} \right)^{1/n} \le 1 \ \ \ \ \ (*)$$ If the inequality $$(*)$$ is an equality then the map $$f$$ will be called a borderline Collatz-like map.
For each (borderline) Collatz-like map $$f$$, we have the (borderline) Collatz-like problem asking whether its iterations diverges nowhere to infinity, i.e. $$\forall n>0, \ \exists m,r>0 \text{ with } f^{\circ (m+r)}(n) = f^{\circ m}(n).$$
If the answer is yes, then let us call $$f$$ an acceptable (borderline) Collatz-like map.

This post focus on a specific family of borderline Collatz-like problems:

For any given $$\alpha >0$$, let us consider the following map $$f_{\alpha}: n \mapsto \left\{ \begin{array}{ll} \left \lfloor{n\alpha} \right \rfloor & \text{ if } n \text{ even,} \\ \left \lfloor{n/\alpha} \right \rfloor & \text{ if } n \text{ odd.} \end{array} \right.$$

The map $$f_{\alpha}$$ is borderline Collatz-like. Let $$S$$ be the set of $$\alpha>0$$ for which $$f_{\alpha}$$ is acceptable.

Question: What is the set $$S$$, explicitly?

It is obvious to find some $$\alpha$$ in $$S$$, and some other out, for example $$S \cap \mathbb{Z}_{>0} = \{ 1 \}$$.

Proposition: $$3/2 \in S$$.
Proof: If $$n$$ is even then $$n=2^ra$$ with $$a$$ odd and $$r>0$$. Then $$f_{3/2}(n)=2^{r-1}3a$$, $$f^{\circ r}_{3/2}(n)=3^ra$$ and $$f^{\circ(r+1)}_{3/2}(n)=3^{r-1}2a = f^{\circ(r-1)}_{3/2}(n)$$. Next, if $$n$$ is odd, then $$n=6k+i$$ with $$i \in \{1,3,5\}$$, and $$\left \lfloor{2n/3} \right \rfloor = \left \lfloor{2(6k+i)/3} \right \rfloor = 6k + \left \lfloor{2i/3} \right \rfloor$$, but $$\left \lfloor{2i/3} \right \rfloor = 0,2,3$$ for $$i=1,3,5$$. So the cases $$i=1,3$$ reduce to the even case, next, if $$i=5$$ then $$\left \lfloor{2n/3} \right \rfloor = 6k+3$$. $$\square$$

Remark: See this comment of user35593 which proves that $$\alpha = 2/3$$ is also in $$S$$.

Now what about $$\alpha$$ irractional? This post (and its comments) provides a family of quadratic integers not in $$S$$ (one of which being the golden ratio $$\phi$$).

Below are the pictures for $$\alpha = \pi, 1/\pi$$ and $$\sqrt{2}$$, of the plot of the map which for every fixed $$n$$ gives the minimal $$m$$ such that $$f_{\alpha}^{\circ (m+r)}(n) = f_{\alpha}^{\circ m}(n)$$ for some $$r$$.

Subquestion 1: Is it true that $$\{\pi, 1/\pi,\sqrt{2} \} \subset S$$?

Then, we could expect that $$\alpha = 1/\sqrt{2}$$ is also in $$S$$, but in fact it seems not! The following picture shows the value of $$\log_{10}(f_{\alpha}^{\circ r}(n))$$ for $$\alpha = 2^{-1/2}$$, $$r=200$$ and $$n<20000$$. Subquestion 2: Is it true that $$2^{-1/2} \not \in S$$?
[for a focus on this specific problem, see this post]

With $$n=15$$ we get the following loop of length $$33$$ $$15, 21, 29, 41, 57, 80, 56, 39, 55, 77, 108, 76, 53, 74, 52, 36, 25, 35, 49, 69, 97, 137, 193, 272, 192, 135, 190, 134, 94, 66, 46, 32, 22, 15, \dots$$The smallest $$n$$ for which the iterations of $$f_{2^{-1/2}}$$ seems to diverge to infinity is $$73$$: $$73, 103, 145, 205, 289, 408, 288, 203, 287, \dots , 102868753471, 145478386303, \dots$$

The difference of shape of the pictures for $$\pi$$ and $$\sqrt{2}$$ is surprising. Below is the picture for $$\alpha = \sqrt{2}^{\sqrt{2}}$$, it is also unsimilar to those above: Moreover, the fact that $$\sqrt{2}, \pi$$ seem to be in $$S$$ and $$\sqrt{2}/2, \phi$$ not, is also surprising because then the answer would be very irregular on the irrational numbers.

All these surprises lead to feel that the answer to the main question could be reachable.

Extended family of (borderline) Collatz-like maps

We can extend the above family as follows: let the tuple $$A=(\alpha_1, \alpha_2, \dots , \alpha_r)$$ such that $$\alpha_i>0$$ for all $$i$$ and $$\prod_i \alpha_i \le 1$$. Consider the map $$f_A: n \mapsto \left \lfloor{n\alpha_i} \right \rfloor \text{ if } n \equiv i \mod (r)$$.

Problem: What are the tuples $$A$$ for which the map $$f_A$$ is acceptable?

Other borderline Collatz-like maps

Here are other examples of boderline Collatz-like maps, provided by Tom Crawford in this Numberphile video (which inspired this post). Let $$\alpha$$ be a normal number in base $$10$$ (you can think to $$\pi$$, which is strongly suspected to be normal). Consider the function $$g_{\alpha}(n)$$ equals to the position of the first occurence of $$n$$ (written in base $$10$$) in the decimal digits of $$\alpha$$. Because $$\alpha$$ is normal, $$g_{\alpha}$$ should satisfy $$(*)$$. Note that $$g_{\pi}$$ is available in OEIS A014777.

Here is an other Collatz-like map involving the set of prime numbers $$\mathbb{P}$$:
First consider the usual bijection $$b: \mathbb{P} \to \mathbb{N}$$, next the map $$g: \mathbb{P} \to \mathbb{P}$$ with $$g(p):= \text{ the greatest prime factor of } 2p+1.$$ Then $$f:= b \circ g \circ b^{-1}$$ should also be a (borderline?) Collatz-like map.
For more details on this map and its generailzations, see this post.

• For $\alpha=\frac{2}{3}$ if you start with an even number you get a smaller number in one step. If we start with an odd number >1 we can write it as $u2^k+1$ where u is odd and $k>0$. Then after $k$ steps we get the even number $u3^k+1$, after $k+1$ steps $2u3^{k-1}$ and after $2k$ steps $u2^k$ so 1 smaller than we started with. Hence we arrived at a smaller number and the sequence will always end at $1$. – user35593 Feb 24 at 12:02
• @user35593: Right! The irregularity of the picture for $2/3$ was a bad indicator on the complexity of this case. – Sebastien Palcoux Feb 24 at 12:12
• Tenth version of the question in a day. – Gerry Myerson Feb 25 at 11:56
• @GerryMyerson meta.mathoverflow.net/q/192/34538 – Sebastien Palcoux Feb 27 at 3:10
• What's your point, Sebastien? – Gerry Myerson Feb 27 at 3:29