Yet another Collatz generalization and conjecture

collatz conjectureconjectureselementary-number-theorysequences-and-series

Observe that Collatz (the $\frac{3n+1}{2}$ version) can be written as: $$n_{i+1}:= \begin{cases}n_i+\left\lceil\frac{n_i}{2}\right\rceil\quad\text{ if odd }n_i \\
n_i-\left\lceil\frac{n_i}{2}\right\rceil\quad\text{ if even }n_i
\end{cases}$$

Looking at it this way gives the following pleasingly simple table for the difference between between consecutive terms, where $\Delta n := n_{i+1}-n_i$:

$$
\begin{array}{|l|l|} \hline
n_i&\Delta n\\ \hline
1&+1 \\ \hline
2&-1 \\ \hline
3&+2 \\ \hline
4&-2 \\ \hline
5&+3 \\ \hline
\ldots&\ldots\\ \hline
\end{array}
$$

I apologize for not having worked out a nice short-form version of this, but consider a generalization of the above to give a construction like:

$$
\begin{array}{|l|l|} \hline
n_i&\Delta n\\ \hline
1&+1 \\ \hline
2&+2 \\ \hline
3&-1 \\ \hline
4&-2 \\ \hline
5&+3 \\ \hline
6&+4 \\ \hline
7&-3 \\ \hline
8&-4 \\ \hline
9&+5 \\ \hline
\ldots&\ldots\\ \hline
\end{array}
$$

In fact, let $k$ be the number determining that cyclic count, so that $k=1$ for the standard Collatz in the first table, and $k=2$ in the second table, and $k=3$ would give $\{1,2,3,-1,-2,-3,4,5,6,-4\ldots\}$. And by that definition, let $f(n,k)$ return the corresponding $\Delta n$ using $k$ as described.

Then the next term for regular Collatz could be found as $C(n):=n+f(n,1)$. More generally, let's define $$C_k(n):=n+f(n,k),$$ so e.g. by examining that second table, we see that $C_2(8)=8-4=4$ and $C_2(9)=14$.

This construction seems like it might have some interesting properties. In particular, I conjecture that

$\forall k,n\in\mathbb N : C_k(n)$ will eventually reach $k$, assuming Collatz itself holds.

Furthermore, if you take any such sequence and number it starting with $S_0=n$, it seems we have

$$\gcd(S_i,k) \leq \gcd(S_{i+1},k).$$

This means that once you have $k|S_j$ for some $j$, all future terms can be divided through by $k$ to give a standard Collatz sequence, but this is definitely not the case before reaching $S_j$.

I'm interested to see if anyone can find a counterexample or simple reason why this should or should not hold. Any reasonably constructive feedback would be acceptable as an answer, and of course if this has been investigated before, by all means let me know.

Sample Mathematica code if anyone wants it:

Clear[f, c];
SetAttributes[{f, c}, Listable];
f[n_, k_] := With[{m = Mod[n, 2 k, 1]}, If[m <= k, 1, -1] (Floor[(n - 1)/(2 k)] (k) + Mod[n, k, 1])]
c[n_, k_] := NestWhileList[# + f[#, k] &, n, # != k &, 1, 1000]

c[27, Range[6]] // Column

will give you sequences for $C_k(27)$ for $k \leq 6$.

Best Answer

This is an interesting idea but the behaviour of the new sequences do follow from the behaviour of the standard series.

For given $k$, if $x_{n+1}<x_n$, then $x_{n+1}$ is divisible by $k$ and thereafter, as you say, the sequence is just $k$ times the standard series.

So, all that needs proving is that one always reaches a multiple of $k$. If $x_{n+1}>x_n$ then, modulo $2k$, $1\le x_n\le k$ and $x_{n+1}\equiv {2x_n}\pmod {2k}$. So, modulo $2k$, the terms of the sequence double each time until a residue greater than $k$ is reached.

Related Question