4

Let $f:\mathbb Z\rightarrow\mathbb Z$ be the function defined by $$f(3n)=2n$$ $$f(3n+1)=4n+1$$ $$f(3n+2)=4n+3$$ Is there any $x\in\mathbb Z$ such that the sequence $x,\,f(x),\,f(f(x)),\,f(f(f(x)),\ldots$ is not periodic?

This question is loosely inspired by an earlier question of mine and I strongly suspect that the answer is "yes" because of similar reasons to the heuristics that suggest the Collatz conjecture to be true: in any interval of $3^n$ consecutive integers and any sequence of $n$ residues mod $3$, there is exactly one $x$ whose trajectory begins with that sequence of mod $3$ residues. However, randomly choosing to multiply by $\frac{2}3$ a third of the time or $\frac{4}3$ otherwise would typically increase the logarithm of a value on iteration - suggesting unbounded trajectories regardless of bijectivity.

If one changed the third line of the definition to read $8n+3$ instead of $4n+3$, the answer would be "yes" because the function would remain injective, but not be surjective - and any starting value not in the image would have a divergent trajectory. However, the given function is bijective - which seems like the next most difficult case - and which I have no clue how to approach (although it seems like, for instance, $x=10$ likely has this property - it has no cycle in its first million terms, at least).

Milo Brandt
  • 60,888
  • 3
    This map has been studied before. No one knows what it does. See https://oeis.org/A028394 for links to the literature. – Gerry Myerson Aug 18 '21 at 13:14
  • Have you had a look at those links? – Gerry Myerson Aug 20 '21 at 12:03
  • 3
    @GerryMyerson I just looked through the papers there (or at least those not behind a paywall) - they constitute a satisfying answer of "This question has been researched and remains open" to this question. Perhaps it would be better if that comment were expanded into an answer? (I could also probably sift through the literature a bit more to try to summarize what's been said of the question - the Lagarias references on OEIS cite quite a bit more material about this function) – Milo Brandt Aug 20 '21 at 22:03
  • Let me generalise something which may help you think about this problem. If $f^m(x)$ let $m$ count the steps and let $T_m(x)=f^m(x)\pmod3$ Then $T_m:\Bbb Z_3\to \Bbb Z_3$ is a bijection on the 3-adics into which the conventional positive integers embed. Every cycle points to a "rational" 3-adic. Integers having terminating sequences map to $p+\overline y_3:y\in{0,1,2}, p\in\Bbb N$. There is a body of work to be carried out categorising which adics $T$ maps to the "rational" adics. You ask whether $\Bbb N$ is in the preimage of the "rational" 3-adics by $T$ or something similar. – it's a hire car baby Sep 06 '21 at 11:37

3 Answers3

1

8 doesn't appear periodic. A few terms of the sequence:

8, 11, 15, 10, 13, 17, 23, 31, 41, 55, ... (My implementation reached a few thousand digits before I decided to spare my laptop.)

It's impossible for a number to enter an orbit it's not a part of, since the function is bijective. So any non-periodic sequence needs to diverge. But these types of results are typically unproven in the case of Collatz-like functions.

jMdA
  • 1,310
0

With: $$0). x=3n : f(x)=2x/3$$ $$1). x=3n+1 : f(x)=(4x-1)/3$$ $$2). x=3n+2 : f(x)=(4x-5)/3$$

Periodic cycle means not infinity, but: $$\frac{f(x)}{x}=(\frac{2}{3}.\frac{4}{3}.\frac{4}{3})^\frac{1}{3}=\frac{2}{3}. 2^\frac{2}{3}>1 : diverge!$$

In fact, one has: $$x \neq f(x):$$ $$0). x\neq2x/3 : true\ if\ x\neq0\ because\ f(0)=0$$ $$1). x\neq(4x-1)/3 : true\ if\ x\neq1\ because\ f(1)=1$$ $$2). x\neq(4x-5)/3 : true\ if\ x\neq5\ because\ f(5)=5$$ So, sequence not periodic of lenght 1 (fixed point) if $x\neq\{0;1;5\}$.

$$x\neq f(f(x)):$$ $$00). x\neq2(2x/3)/3 : true\ if\ x\neq0$$ $$01). x\neq(4(2x/3)-1)/3 : true\ if\ x\neq-3$$ $$02). x\neq(4(2x/3)-5)/3 : true\ if\ x\neq-15$$ $$10). x\neq2((4x-1)/3)/3 : true\ if\ x\neq-2$$ $$11). x\neq(4(4x-1)/3-1)/3 : true\ if\ x\neq1$$ $$12). x\neq(4(4x-1)/3-5)/3 : true\ if\ x\neq19/7$$ $$20). x\neq2((4x-5)/3)/3 : true\ if\ x\neq-10$$ $$21). x\neq(4(4x-5)/3-1)/3 : true\ if\ x\neq23/7$$ $$22). x\neq(4(4x-5)/3-5)/3 : true\ if\ x\neq5$$ So, sequence not periodic of lenght 2 if $x\neq\{-15;-10;-3;-2;0;1;5\}$. None new value in $Z^+$.

and go on to maybe find at least another no cycle of lenght >2.

myidea
  • 1
0

Integers of the form 4n+1 play a particular role in Collatz but in number theory in general: see for example the legendary one-sentence proof from Zagier that any prime that can be written 4n+1 is the sum of two squares

https://people.mpim-bonn.mpg.de/zagier/files/doi/10.2307/2323918/fulltext.pdf

Now back to Collatz, if any odd x number can be written 4o+1 with o odd, then x and o are mapped to the same number. This fundamental property is very useful to study the attractor of any number under the Collatz map.

In this paper, we did exactly that, define the attractor of any number:

https://www.mdpi.com/2227-7390/9/16/1898

What you will see is that action 3n has the peculiar property that if n can be written 2x+1 with x odd, then 3n can be written 4y+1, and vice versa: if n can be written 4x+1 then 3n can be written 2y+1 with y odd

also, f(3n+2)= 4n+3 has the property of mapping some odd numbers backward. For example, it will map 11 to 15 while the Collatz map has 15 orbit to 23 which in turn can be proven to be equivalent to 11 (see rule 2 of our paper)

If you dig deeper into the five rules we published, it should enlighten your question.

Idriss Aberkane
  • 9