8
$\begingroup$

In an alternative version of Collatz problem, one iterates the function $f:\mathbb{N}\to\mathbb{N}$ defined by $$f(n)=\begin{cases}n/3 &\mbox{if}\ n\equiv0\ (\mbox{mod}3)\\ 2n+1&\mbox{if}\ n\equiv1\ (\mbox{mod}3)\\ 2n+2&\mbox{if}\ n\equiv2\ (\mbox{mod}3) \end{cases}$$

There are two cycles: $\{1,3\}$ and $\{2,6\}$. Starting from any $n$ in $\mathbb N$, one ends up in $\{1,3\}$ or in $\{2,6\}$.

To show this, use induction. The desired property holds for $n=1$ and $n=2$, obviously. If it holds for every $m<n$, then:

  • if $n=3k$, then $f(n)=k$ and $k<3k=n$ hence, by the induction hypothesis, some number of iterations of $f$ brings $k$ to the cycle $\{1,3\}$ or to the cycle $\{2,6\}$;
  • if $n=3k+1$, then $f(n)=6k+3$, $f(f(n))=2k+1$ and $2k+1<3k+1=n$ hence, by the induction hypothesis, some number of iterations of $f$ brings $2k+1$ to the cycle $\{1,3\}$ or to the cycle $\{2,6\}$;
  • if $n=3k+2$, then $f(n)=6k+6$, $f(f(n))=2k+2$ and $2k+2<3k+2=n$ hence, by the induction hypothesis, some number of iterations of $f$ brings $2k+2$ to the cycle $\{1,3\}$ or to the cycle $\{2,6\}$.

Given any number $n$, let $c(n)=1$ if, starting at $n$ and iterating $f$, one ends in the $\{1,3\}$ cycle, and $c(n)=2$ if one ends in the $\{2,6\}$ cycle. The table of the first values of $c(n)$ is as follows:

\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\ \hline c(n)&1&2&1&1&1&2&1&2&1&1&2&1&1&1&1&2&1&2&1&1\\ \end{array}

Is there any way to characterize numbers $n$ according to $c(n)$, the cycle they fall into? In other words, what can be proved about the set $\{n\in\mathbb N\mid c(n)=1\}$?

$\endgroup$
10
  • 1
    $\begingroup$ I think this sequence pretty much contains every number with $c=2$. $\endgroup$
    – DHMO
    Apr 19, 2017 at 12:54
  • 1
    $\begingroup$ @Dario is not directly related, but when I saw that you are playing with a different modularity ($3$) it reminded me a more generic version I tried long time ago to study, so just in case you are curious: math.stackexchange.com/questions/1232344/… $\endgroup$
    – iadvd
    Apr 20, 2017 at 9:31
  • 1
    $\begingroup$ Maybe a simpler question: which of the cycles attracts the most numbers? For an interval (N, 2N) for large N, how many of them do we expect to have c=1? Are there some heuristics which predict what is going on? $\endgroup$
    – TMM
    Apr 22, 2017 at 10:57
  • $\begingroup$ @DHMO: Your guess seems to be correct, at least by looking at my trials with mathematica (even if I'm not really sure how the sequence you linked is constructed), but if, as it seems, they coincide there are few hopes to get an enlightening characterization. $\endgroup$
    – Dario
    Apr 22, 2017 at 14:21
  • $\begingroup$ @TMM: I tried to check with mathematica your suggestion, and in the interval (50000,100000) the number falling in the $c=2$ cycle is around the 30%. $\endgroup$
    – Dario
    Apr 22, 2017 at 14:25

1 Answer 1

3
$\begingroup$

Remark: this answer is not yet a complete answer, possibly a complete answer cannot be given


A good ansatz to define such a "character according to the cycle they fall into" is possibly to write down the reverse-iterates $C(a,A)$ beginning at root $r_1=1$ and at root $r_2=2$ and to create the two trees of numbers.

Preliminaries: To make things a bit more compact, let's redefine our transformation-rule:

  1. Assume $ a \in \Bbb N^+ \backslash 3 $ for example $a \in \{1,2,4,5,7,8,\ldots \} $
  2. Define $\quad T(a) \overset{\text{def}}= {2a+(a \% 3) \over 3^A} \quad$ where "$a\%b$" means the residue of integer division of $a$ by $b$ as in some programming languages
  3. The inverse of $T(a)$ is then $\quad C(a,A)={3^Aa-2+(a \% 2) \over 2 } \quad $ where $A \in \Bbb N^+$ is now an additional free parameter

Tree generating from root $r_1=1$:
Let us consider that numbers, which, by one transformation fall down to $1$: of course, that are firstly all numbers $a_A(1) = 1 \cdot 3^A $ where $ A \in \Bbb N^+$ . But by our definition of the numbers $a$ that we want to look at we can omit that (trivial) considerations here.

So let us look at that numbers $a_k$ which have the property that $T(a)=1$. This are all numbers $C(1,A)= { 1 \cdot3^A -2 + (1) \over 2} = { 3^A -1 \over 2} $ giving the vector of results $[a_{A}(1)]_{A>0}=[1,4,13,40,121,\ldots ]$

Next we use at each of those numbers and find all numbers $a_B(a_A(1)) = C(a_A(1),B)$. For $A=B=1$ this results in the value $1$ and is thus the "trivial cycle" on number $1$ and for $A=1, B>1$ we simply get back the same vector which we already have.
So we look at $a_B(a_A(1)) ; A \ge 2$ which means $a_B(4), a_B(13), a_B(40), \ldots $ and getting infinite vectors of numbers for each of them.
For $a_B(4)$ we get the vector $[a_B(4)]_{B\gt 0}=[5,17,53,161,\ldots]$
For $a_B(13)$ we get the vector $[a_B(13)]_{B\gt 0}=[19,58,175,\ldots]$
and so on.
I've made a little picture for the beginning of that tree, rooted on the first root $r_1=1$: picture
Some properties are immediately visible:

  1. The yellow boxes.
    a. They have an odd "parent"
    ("parent" means: all numbers of the box transform to that "parent" by the $T()$-transformation).
    Example: the box with first element $19$ has "parent" $13$ because $T(19)=13$ (and of course $T(13)=1=r_1$ so $19$ falls down to the first root).

    b. The progression in the box is $a_{k+1}=3a_k+1$.
    c. The numbers are alternatively odd and even.
    d. The numbers are $1 \pmod 3$.

  2. The green boxes.
    a. They have an even "parent".
    Example: the box with first element $5$ has "parent" $4$ because $T(5)=4$ (and $T(4)=1=r_1$ ).
    b. The progression in the box is $a_{k+1}=3a_k+2$.
    c. The numbers have all the same parity; they are either all odd or all even (possibly depending on the factor power-of-2 in their parent, didn't check this).
    d. The numbers are $2 \pmod 3$.


Provisorical resume: This should be enough for the beginning. The analoguous tree for the root $r_2=2$ can be constructed analoguously. I've not yet a simpler formula for the accordances of the numbers in the trees with their roots.

The trees of $a$ sorted as increasing sequences, according to their roots:
for $r_1$ oeis A183213
for $r_2$ oeis A178931
(note, that the OEIS-sequences have the numbers from the trees and all multiples by powers of 3)

We can relate that tree to the explanation in the OEIS-sequences, which deal with the floor-function and the relation is intransparent at first glance. But we can note, that we can generate our tree using the floor-function as well.
Let $a_i$ denote the elements from the vector $[1,4,13,40,...]$ (which fall down to root $r_1=1$ by one step) such that we have $$a_i \underset{i \gt 0}= \left \lfloor {r_1 3^i-1\over 2} \right \rfloor $$.
Then we can recursively denote the elements of their "children" by a second index $j>0$ writing $$a_{i,j} \underset{i,j \gt 0} =\left \lfloor { a_i \cdot 3^j-1\over 2} \right \rfloor $$ and can immediately recurse arbitrarily deep by adding more indices: $$a_{i,j,k} \underset{i,j,k \gt 0} =\left \lfloor { a_{i,j} \cdot 3^k-1\over 2} \right \rfloor $$ $$a_{i,j,k,l} \underset{i,j,k,l \gt 0} =\left \lfloor { a_{i,j,k} \cdot 3^l-1\over 2} \right \rfloor $$ and so on.
For instance, the entry $22$ in the lower box in the above picture would have the index $a_{2,1,2}$ and this should be computed by $$\begin{array}{} a_2 &= \left \lfloor {r_1 \cdot 3^2 -1 \over 2} \right \rfloor &= 4 \\ a_{2,1} &= \left \lfloor {4 \cdot 3^1-1 \over 2} \right \rfloor &= 5 \\ a_{2,1,2} &= \left \lfloor {5 \cdot 3^2-1 \over 2} \right \rfloor &= 22 \\ \end{array}$$

This scheme using the floor function seems to agree with some of the given formulae in the comments at the OEIS-sequences and their linked "eigen-sequences".


The tree from root $r_2$
tree_2

Context-remark: it might be instructive to compare similar trees for the collatz-problem (only the graphic is a bit more primitive, especially the representation of the numbers in the digitsystem to base 2 (there) resp base 3 (here) . See here and click to "About numerical and graphical trees" (subpage without frame)

$\endgroup$
2
  • $\begingroup$ Nice explanation! Do you know in which context the sequences you linked are studied? Because, according to the OEIS website, they are defined studying some trees, but the definition of the tree itself seems quite arbitrary to me. Do these kind of trees naturally appear somewhere (apart from these Collatz-like problems)? $\endgroup$
    – Dario
    Apr 22, 2017 at 14:50
  • 1
    $\begingroup$ @Dario - no, unfortunately I've seen that sequences only today, by suggestion of DHMO, and I've not yet an idea what considerations lead to that sequences/trees. (Note the concept of "eigen-sequence" in one link in the OEIS-sequence) I think I can come t back to this only tomorrow, let's see. Perhaps I get some more ideas myself... $\endgroup$ Apr 22, 2017 at 17:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .