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:

$$\textstyle H(n)\equiv n+\left\lfloor {\frac {1}{2}}n\right\rfloor ={\Big \lfloor }{\frac {3}{2}}n{\Big \rfloor }={\begin{cases}{\frac {3n}{2}}&{\text{if }}n\equiv 0{\pmod {2}}\\{\frac {3n-1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}\\\end{cases}}$$

which can alternatively be written as

$${\begin{array}{l}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\leq k\leq s$ be an integer and $H^{k}$ is the $k$th iterate of $H$.

$${\begin{array}{l}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{cases}{\frac {3\times a(n)+6}{2}}&{\text{if }}a(n)\equiv 0{\pmod {2}}\\{\frac {3\times a(n)+3}{2}}&{\text{if }}a(n)\equiv 1{\pmod {2}}\end{cases}}$$

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{cases}{\frac {3\times a(n)+4}{2}}&{\text{if }}a(n)\equiv 0{\pmod {2}}\\{\frac {3\times a(n)+3}{2}}&{\text{if }}a(n)\equiv 1{\pmod {2}}\end{cases}}$$

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}{l}b(n+1)&=&{\frac {1}{3}}a(n+1)+2\\b(n+1)&=&2+{\frac {1}{3}}{\begin{cases}{\frac {3\times a(n)+6}{2}}&{\text{if }}a(n)\equiv 0{\pmod {2}}\\{\frac {3\times a(n)+3}{2}}&{\text{if }}a(n)\equiv 1{\pmod {2}}\end{cases}}\\b(n+1)&=&{\begin{cases}{\frac {a(n)+6}{2}}&{\text{if }}a(n)\equiv 0{\pmod {2}}\\{\frac {a(n)+5}{2}}&{\text{if }}a(n)\equiv 1{\pmod {2}}\end{cases}}\\b(n+1)&=&{\begin{cases}{\frac {3(b(n)-2)+6}{2}}&{\text{if }}3(b(n)-2)\equiv 0{\pmod {2}}\\{\frac {3(b(n)-2)+5}{2}}&{\text{if }}3(b(n)-2)\equiv 1{\pmod {2}}\end{cases}}\\b(n+1)&=&{\begin{cases}{\frac {3b(n)}{2}}&{\text{if }}b(n)\equiv 0{\pmod {2}}\\{\frac {3b(n)-1}{2}}&{\text{if }}b(n)\equiv 1{\pmod {2}}\end{cases}}\\\end{array}}$$

For Antihydra, we can repeat this but with the sequence $b(n)=a(n)+4$.