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
)
≡
n
+
⌊
1
2
n
⌋
=
⌊
3
2
n
⌋
=
{
3
n
2
if
n
≡
0
(
mod
2
)
3
n
−
1
2
if
n
≡
1
(
mod
2
)
{\displaystyle \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
H
(
2
n
)
=
3
n
H
(
2
n
+
1
)
=
3
n
+
1
{\displaystyle {\begin{array}{l}H(2n)&=&3n\\H(2n+1)&=&3n+1\\\end{array}}}
It has some connections to
Mahler's 3/2 problem .
Relationship to Hydra and Antihydra Recall the high-level rules for Hydra and Antihydra:
Hydra
Antihydra
Let
C
(
a
,
b
)
:=
0
∞
<A
2
0
a
3
b
2
0
∞
{\displaystyle C(a,b):=0^{\infty }\;{\textrm {<A}}\;2\;0^{a}\;3^{b}\;2\;0^{\infty }}
0
∞
A>
0
∞
→
20
C
(
3
,
0
)
,
C
(
2
a
,
0
)
→
6
a
2
+
20
a
+
4
0
∞
3
3
a
+
1
1
A>
2
0
∞
,
C
(
2
a
,
b
+
1
)
→
6
a
2
+
23
a
+
10
C
(
3
a
+
3
,
b
)
,
C
(
2
a
+
1
,
b
)
→
4
b
+
6
a
2
+
23
a
+
26
C
(
3
a
+
3
,
b
+
2
)
.
{\displaystyle {\begin{array}{|lll|}\hline 0^{\infty }\;{\textrm {A>}}\;0^{\infty }&\xrightarrow {20} &C(3,0),\\C(2a,0)&\xrightarrow {6a^{2}+20a+4} &0^{\infty }\;3^{3a+1}\;1\;{\textrm {A>}}\;2\;0^{\infty },\\C(2a,b+1)&\xrightarrow {6a^{2}+23a+10} &C(3a+3,b),\\C(2a+1,b)&\xrightarrow {4b+6a^{2}+23a+26} &C(3a+3,b+2).\\\hline \end{array}}}
A
(
a
,
b
)
:=
0
∞
1
a
0
1
b
E>
0
∞
{\displaystyle A(a,b):=0^{\infty }\;1^{a}\;0\;1^{b}\;{\textrm {E>}}\;0^{\infty }}
0
∞
A>
0
∞
→
11
A
(
0
,
4
)
,
A
(
a
,
2
b
)
→
2
a
+
3
b
2
+
12
b
+
11
A
(
a
+
2
,
3
b
+
2
)
,
A
(
0
,
2
b
+
1
)
→
3
b
2
+
9
b
−
1
0
∞
<F
110
1
3
b
0
∞
,
A
(
a
+
1
,
2
b
+
1
)
→
3
b
2
+
12
b
+
5
A
(
a
,
3
b
+
3
)
.
{\displaystyle {\begin{array}{|lll|}\hline 0^{\infty }\;{\textrm {A>}}\;0^{\infty }&\xrightarrow {11} &A(0,4),\\A(a,2b)&\xrightarrow {2a+3b^{2}+12b+11} &A(a+2,3b+2),\\A(0,2b+1)&\xrightarrow {3b^{2}+9b-1} &0^{\infty }\;{\textrm {<F}}\;110\;1^{3b}\;0^{\infty },\\A(a+1,2b+1)&\xrightarrow {3b^{2}+12b+5} &A(a,3b+3).\\\hline \end{array}}}
Already, both machines can be observed to have very similar functions. Both have one parameter that increases exponentially with growth factor
3
2
{\textstyle {\frac {3}{2}}}
Hydra
Antihydra
a
0
=
3
,
a
n
+
1
=
{
3
a
n
+
6
2
if
a
n
≡
0
(
mod
2
)
3
a
n
+
3
2
if
a
n
≡
1
(
mod
2
)
{\displaystyle a_{0}=3,a_{n+1}={\begin{cases}{\frac {3a_{n}+6}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+3}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {2}}\end{cases}}}
a
0
=
4
,
a
n
+
1
=
{
3
a
n
+
4
2
if
a
n
≡
0
(
mod
2
)
3
a
n
+
3
2
if
a
n
≡
1
(
mod
2
)
{\displaystyle a_{0}=4,a_{n+1}={\begin{cases}{\frac {3a_{n}+4}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+3}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {2}}\end{cases}}}
Now, we will introduce a new integer sequence based on the old one and discover the recursive rules for that sequence. For Hydra, this new sequence is
b
n
=
1
3
a
n
+
2
{\textstyle b_{n}={\frac {1}{3}}a_{n}+2}
b
n
=
a
n
+
4
{\displaystyle b_{n}=a_{n}+4}
b
n
+
1
{\displaystyle b_{n+1}}
a
n
+
1
{\displaystyle a_{n+1}}
Hydra
Antihydra
b
0
=
3
,
b
n
+
1
=
{
a
n
+
6
2
if
a
n
≡
0
(
mod
2
)
a
n
+
5
2
if
a
n
≡
1
(
mod
2
)
{\displaystyle b_{0}=3,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
0
=
8
,
b
n
+
1
=
{
3
a
n
+
12
2
if
a
n
≡
0
(
mod
2
)
3
a
n
+
11
2
if
a
n
≡
1
(
mod
2
)
{\displaystyle b_{0}=8,b_{n+1}={\begin{cases}{\frac {3a_{n}+12}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+11}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {2}}\end{cases}}}
After that, we must substitute
a
n
{\displaystyle a_{n}}
b
n
{\displaystyle b_{n}}
Hydra
Antihydra
b
0
=
3
,
b
n
+
1
=
{
3
(
b
n
−
2
)
+
6
2
if
3
(
b
n
−
2
)
≡
0
(
mod
2
)
3
(
b
n
−
2
)
+
5
2
if
3
(
b
n
−
2
)
≡
1
(
mod
2
)
{\displaystyle b_{0}=3,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
0
=
8
,
b
n
+
1
=
{
3
(
b
n
−
4
)
+
12
2
if
b
n
−
4
≡
0
(
mod
2
)
3
(
b
n
−
4
)
+
11
2
if
b
n
−
4
≡
1
(
mod
2
)
{\displaystyle b_{0}=8,b_{n+1}={\begin{cases}{\frac {3(b_{n}-4)+12}{2}}&{\text{if }}b_{n}-4\equiv 0{\pmod {2}}\\{\frac {3(b_{n}-4)+11}{2}}&{\text{if }}b_{n}-4\equiv 1{\pmod {2}}\end{cases}}}
We finish by noting that the if statements simplify to simply checking if
b
n
{\displaystyle b_{n}}
Hydra
Antihydra
b
0
=
3
,
b
n
+
1
=
{
3
b
n
2
if
b
n
≡
0
(
mod
2
)
3
b
n
−
1
2
if
b
n
≡
1
(
mod
2
)
{\displaystyle b_{0}=3,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}}}
b
0
=
8
,
b
n
+
1
=
{
3
b
n
2
if
b
n
≡
0
(
mod
2
)
3
b
n
−
1
2
if
b
n
≡
1
(
mod
2
)
{\displaystyle b_{0}=8,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}}}
Properties Here,
s
{\displaystyle s}
t
{\displaystyle t}
t
{\displaystyle t}
0
≤
k
≤
s
{\displaystyle 0\leq k\leq s}
H
k
{\displaystyle H^{k}}
k
{\displaystyle k}
H
{\displaystyle H}
H
k
(
2
s
t
)
=
3
k
2
s
−
k
t
H
k
(
2
s
t
+
1
)
=
3
k
2
s
−
k
t
+
1
{\displaystyle {\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}}}
