Hydra function

A bitmap depiction of 255 iterations of the Hydra function, starting with 3 at the top.

The Hydra function is a Collatz-like function whose behavior is connected to the unsolved halting problems for the Cryptids Hydra and Antihydra. It is defined as: $$H(n)\equiv n+\lfloor \frac{1}{2}n\rfloor =\lfloor \frac{3}{2}n\rfloor =\{\begin{array}{ll}\frac{3n}{2}& \text{if }n\equiv 0(\mathrm{mod}2)\\ \frac{3n-1}{2}& \text{if }n\equiv 1(\mathrm{mod}2)\\ \end{array}$$ which can alternatively be written as $$\begin{array}{lll}H(2n)& =& 3n\\ H(2n+1)& =& 3n+1\\ \end{array}$$ It has some connections to Mahler's 3/2 problem.

Properties

Here, $s$ and $t$ are positive integers with $t$ odd. Let $0\le k\le s$ be an integer and $H^k$ is the $k$th iterate of $H$. $$\begin{array}{lll}{H}^k(2^{s}t)& =& 3^k{2}^{s-k}t\\ H^k(2^{s}t+1)& =& 3^k{2}^{s-k}t+1\\ \end{array}$$

Relationship to Hydra and Antihydra

Both machines effectively track the progress of two variables; one of them changes depending on its value modulo 2 but roughly multiplies itself by $\frac{3}{2}$, and the other increases by 2 or decreases by 1 depending on the parity of the first variable.

In particular, Hydra halts if and only if the sequence $$a(n+1)=\{\begin{array}{ll}\frac{3\times a(n)+6}{2}& \text{if }a(n)\equiv 0(\mathrm{mod}2)\\ \frac{3\times a(n)+3}{2}& \text{if }a(n)\equiv 1(\mathrm{mod}2)\end{array}$$ ever has more even terms than twice the number of odd terms, starting with $a(0)=3$. Similarly, Antihydra halts if and only if the sequence $$a(n+1)=\{\begin{array}{ll}\frac{3\times a(n)+4}{2}& \text{if }a(n)\equiv 0(\mathrm{mod}2)\\ \frac{3\times a(n)+3}{2}& \text{if }a(n)\equiv 1(\mathrm{mod}2)\end{array}$$ ever has more odd terms than twice the number of even terms, starting with $a(0)=4$.

For Hydra, we can introduce the sequence $b(n)=\frac{1}{3}a(n)+2$ whose terms have the same sequence of parities as $a(n)$. Then we have: $$\begin{array}{lll}b(n+1)& =& \frac{1}{3}a(n+1)+2\\ b(n+1)& =& 2+\frac{1}{3}\{\begin{array}{ll}\frac{3\times a(n)+6}{2}& \text{if }a(n)\equiv 0(\mathrm{mod}2)\\ \frac{3\times a(n)+3}{2}& \text{if }a(n)\equiv 1(\mathrm{mod}2)\end{array}\\ b(n+1)& =& \{\begin{array}{ll}\frac{a(n)+6}{2}& \text{if }a(n)\equiv 0(\mathrm{mod}2)\\ \frac{a(n)+5}{2}& \text{if }a(n)\equiv 1(\mathrm{mod}2)\end{array}\\ b(n+1)& =& \{\begin{array}{ll}\frac{3(b(n)-2)+6}{2}& \text{if }3(b(n)-2)\equiv 0(\mathrm{mod}2)\\ \frac{3(b(n)-2)+5}{2}& \text{if }3(b(n)-2)\equiv 1(\mathrm{mod}2)\end{array}\\ b(n+1)& =& \{\begin{array}{ll}\frac{3b(n)}{2}& \text{if }b(n)\equiv 0(\mathrm{mod}2)\\ \frac{3b(n)-1}{2}& \text{if }b(n)\equiv 1(\mathrm{mod}2)\end{array}\\ \end{array}$$ For Antihydra, we can repeat this but with the sequence $b(n)=a(n)+4$.