1
$\begingroup$

Given $a_0$ be an positive integer, define

$$ a_{n+1} = \begin{cases} 8a_n, & \text{if $a_n$ is odd} \\ \lfloor a_n/3\rfloor, & \text{if $a_n$ is even} \end{cases}$$

Now form the sequence $(a_n)_{n\in \mathbb{N}}$ by performing this operation repeatedly.

Example: $a_0=11,(a_n)_{n\in\mathbb{N}}=(11,88,29,232,77,616,205,1640,546,182,60,20,6,2,0,0,...)$

1 Question: For every $a_0,(a_n)_{n\mathbb{N}}$ will eventually reach the number $0$?

The above claim is true for all $a_0$ up to $10^6$.

Keith Matthews enlarge conjecture to trajectories starting with a negative integer. Go through Keith Matthews programming to insure mapping, link

Extended Claim

Let $a_0$ be an positive integer and $k$ be any odd positive integer greater than $1$, define

$$ a_{n+1} = \begin{cases} (k^2-1)a_n, & \text{if $a_n$ is odd} \\ \lfloor a_n/k\rfloor, & \text{if $a_n$ is even} \end{cases}$$

Now form the sequence $(a_{n,k})_{n\in \mathbb{N}}$ by performing this operation repeatedly

Example $a_0=11,k=5,(a_{n,5})_{n\in\mathbb{N}}=(11,264,52,10,2,0,0,...)$

2 Question: For every $a_0$ and odd $k\ge 3$ the sequence $(a_{n,k})_{n\mathbb{N}}$ will eventually reach the number $0$?

Programming for extended claim by Keith Matthews, including negative values, link

Extended Collatz conjecture

Let $a_0$ be an positive integer and $k$ be any even positive integer, define

$$ a_{n+1} = \begin{cases} (k+1)a_n+1, & \text{if $a_n$ is odd} \\ \lceil a_n/k\rceil, & \text{if $a_n$ is even} \end{cases}$$

Now form the sequence $(a_{n,k})_{n\in \mathbb{N}}$ by performing this operation repeatedly

Example $a_0=5,k=4,(a_{n,k})_{n\in\mathbb{N}}=(5,26,7,36,9,46,12,3,16,4,1,...)$

again we can ask about, every sequence will eventually reach at the number $1$?

Programming for extended Collatz conjecture by Keith Matthews, including negative values, link

More on extended Collatz conjecture

First: Let $a_0,t$ be an positive integer and $k$ be any even positive integer, define

$$ a_{n+1} = \begin{cases} (k^t+k^{t-1})a_n+k^{t-1}, & \text{if $a_n$ is odd} \\ \lceil a_n/k\rceil, & \text{if $a_n$ is even} \end{cases}$$

Now form the sequence $(a_{n,k,t})_{n\in \mathbb{N}}$ by performing this operation repeatedly then sequence will eventually reach at the number $1$

Second: Let $a_0$ be an positive integer and $k$ be any even positive integer greater than $2$ and $t\in\mathbb{Z}_{\ge 2}$, define

$$ a_{n+1} = \begin{cases} (k^t+k^{t-2})a_n+k^{t-2}, & \text{if $a_n$ is odd} \\ \lceil a_n/k\rceil, & \text{if $a_n$ is even} \end{cases}$$

Now form the sequence $(a_{n,k,t})_{n\in \mathbb{N}}$ by performing this operation repeatedly then sequence will eventually reach at the number $1$


I again extend claim on odd $k$

First: Let $a_0$ be an positive integer and $k$ be any odd positive integer greater than $1$ and $t\in\mathbb{Z}_{\ge 2}$, define

$$ a_{n+1} = \begin{cases} (k^t-k^{t-2})a_n, & \text{if $a_n$ is odd} \\ \lfloor a_n/k\rfloor, & \text{if $a_n$ is even} \end{cases}$$

Then the sequence $(a_{n,k,t})_{n\in \mathbb{N}}$ will eventually reach at the number $0$

Second: Let $a_0$ be an positive integer and $k$ be any odd positive integer greater than $1$ and $t\in\mathbb{Z}_{\ge 1}$, define

$$ a_{n+1} = \begin{cases} (k^t-k^{t-1})a_n, & \text{if $a_n$ is odd} \\ \lfloor a_n/k\rfloor, & \text{if $a_n$ is even} \end{cases}$$

Then the sequence $(a_{n,k,t})_{n\in \mathbb{N}}$ will eventually reach at the number $0$

$\endgroup$
7
  • 5
    $\begingroup$ This does not seem any easier than the Collatz conjecture. $\endgroup$
    – GH from MO
    Dec 6 '20 at 20:39
  • 3
    $\begingroup$ Without getting into exact definitions, the problem "Given a 'Collatz-like' function $g$, does $g^k(n)$ eventually equal $1$ for all $n \in \mathbb{N}$?" is undecidable, due to Kurtz & Simon. Your question is in some sense akin to asking whether a specific group presentation has decidable word problem, or whether a fixed Turing machine $T$ halts. That could be interesting (certainly it is interesting e.g. when that Turing machine encodes the Collatz problem itself) but as it currently stands, it's just a question in an infinite family of questions, with nothing to distinguish it from the rest. $\endgroup$ Dec 7 '20 at 9:01
  • $\begingroup$ @Carl-Fredrik, I thought that result was due to Conway ("Unpredictable iterations"). $\endgroup$ Dec 7 '20 at 12:18
  • 1
    $\begingroup$ @GerryMyerson Conway showed it is undecidable uniformly in $g$ and $n$. That is, Conway's input is a fixed Collatz-like function $g$ and a natural number $n$. Kurtz & Simon just take a function $g$ as input. $\endgroup$ Dec 7 '20 at 13:09
  • $\begingroup$ @Carl-FredrikNybergBrodda To clarify, I believe you mean this question is akin to whether a fixed Turing machine halts on every input, is that right? $\endgroup$
    – Wojowu
    Dec 7 '20 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.