This is the prior post with the answer to hydra(5). In this post, we’ll be providing the exact sequence for the general hydra problem.
Also wikipedia page: https://en.wikipedia.org/wiki/Hydra_game
See the previous post for an explanation of how the game is played, and the notation I’m using:
([a, b, c, d, e, …, n], S)
Feel free to scroll down to the solution if the proof isn’t of interest.
\((a)\ ([1], S) \rightarrow S;\ \text{on the S-th step, the last head is chopped}\)
\((b)\ ([1 + a, \ldots], S) \rightarrow ([1, \ldots], S + a)\)
Starting with b = 1:
\((c)\ ([1, 1+1, \ldots], S) \rightarrow ([1 + S, 1, \ldots], S + 1) \to ([1, 1, \ldots], 2 \cdot (S + 1) - 1)\)
Let’s define the function that decrements the 2nd index by 1 as B(x):
\(B(x) = 2\cdot(S+1) - 1\)
And generally define the n-th nesting of any function to be:
\(F^n(x) = \underbrace{F(F(\cdots F}_{n\, \text{times}}(x)\cdots))
\)
Continuing with B = 2:
\((d)\ ([1, 1+2, \ldots], S) \rightarrow ([1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1 + 1, \ldots], 2 \cdot (S + 1) - 1) \)
\((d, cont) \to ([1, 1, \ldots], 2 \cdot (2 \cdot(S + 1) - 1 + 1) - 1) \to ([1, 1, \ldots], 4 \cdot (S + 1) - 1)\)
Noticing the same trend as b = 1, generalizing the function B:
\((e)\ ([1, 1+b, \ldots], S) \to ([1, 1, \ldots], 2^b \cdot (S + 1) - 1)\)
and if … is all 0’s, then:
\((f)\ ([1, b], S) \to ([1], 2^{b} \cdot (S + 1) - 1) \to 2^{b}\cdot(S+1) - 1, \text{per (a) & (e)}\)
Quick sanity check, hydra(2) = 3, which this formula conforms to.
Generally:
\(2^{b}\cdot(S+1) - 1 = B^b(S)\)
Starting with c = 1:
\((g)\ ([1, 1, 1+1, \ldots], S) \rightarrow ([1, 1 + S, 1, \ldots], S + 1) \to ([1, 1, 1, \ldots], 2^S \cdot (S + 2) - 1 = B^S(S + 1))\)
Let’s define a function C(x):
\(C(x) = B^x(x+1) = 2^S\cdot(S+2) - 1\)
\((g, rewritten)\ ([1, 1, 1+1, \ldots], S) \to C(S)\)
with c = 2:
\((h)\ ([1, 1, 1+2, \ldots], S) \to ([1, 1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1, 1 + 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], C^2(S))\)
generalizing…
\((i)\ ([1, 1, 1+c, \ldots], S) \to ([1, 1 + S, 1 + c - 1, \ldots], S + 1) \to ([1, 1, 1 + c - 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], C^c(S))\)
if … were 0’s:
\((j)\ ([1, 1, c], S) \to ([1, 1 + S, c - 1], S + 1) \to ([1, 1, c - 1], C(S)) \to ([1, 1, 0], C^c(S))\)
\((j, cont) \to ([1, 0, 0], B(C^c(S))) \to B(C^c(S))\)
Quick sanity check for hydra(3) = 11:
\(([1, 1, 1], 1) \to B(C(1)) = 2 \cdot (C(1) + 1) - 1 = 2 \cdot (2^1 \cdot (1 + 2) - 1) + 1) - 1 = 11\)
Starting with d = 1:
\((k)\ ([1, 1, 1, 1+1, \ldots], S) \to ([1, 1, 1 + S, 1, \ldots], S + 1) \to ([1, 1, 1, 1, \ldots], C^S(S+1))\)
Let’s define a function D(x):
\((k, rewritten)\ ([1, 1, 1, 1+1, \ldots], S) \to D(S)\)
with d = 2:
\((l)\ ([1, 1, 1, 1+2, \ldots], S) \to ([1, 1, 1 + S, 1 + 1, \ldots], S + 1) \to ([1, 1, 1, 1 + 1, \ldots], D(S)) \to ([1, 1, 1, \ldots], D^2(S))\)
generalizing…
\((m)\ ([1, 1, 1, 1+d, \ldots], S) \to ([1, 1, 1 + S, 1 + d - 1, \ldots], S + 1) \to ([1, 1, 1, 1 + d - 1, \ldots], C(S)) \to ([1, 1, 1, \ldots], D^d(S))\)
if … were 0’s:
\((n)\ ([1, 1, 1, d], S) \to ([1, 1, 1 + S, d - 1], S + 1) \to ([1, 1, d - 1], D(S)) \to ([1, 1, 1, 0], D^d(S))\)
\((n, cont) \to ([1, 0, 0, 0], B(C(D^d(S)))) \to B(C(D^d(S)))\)
Quick sanity check for hydra(4) = 1114111:
\(B(C(D(1))) = B(C(C^1(1 + 1))) = B(C(B^2(2 + 1))) = B(C(2^2\cdot (3 + 1) - 1))\)
\( = B(C(15)) = B(2^{15} * (15 + 2) - 1) = B(557055) = 2 \cdot ( 557055 + 1) - 1 = 1114111\)
Let’s define a function that describes the number of cuts required to decrement the i-th depth of the hydra while cleaning up the subsequent spawned heads:
\(([1, 1, 1, \ldots, h_i, \ldots], x) \to ([1, 1, 1, \ldots, h_i - 1, ...], F_i(x))\)
Then, based on what’s been demonstrated in the iterated section:
\(F_{i+1}(x) = F_i^x(x + 1)\)
\(where\ F_1(x) = 2\cdot(x + 1) - 1 = 2x + 1\)
And the answer to the linear hydra game of depth n is:
\(F_1(F_2(F_3(\ldots F_{n-1}(F_n(1))\ldots)))\)
To figure out any arbitrary hydra configuration, ([a, b, c, d, e, f, … ], S) you nest the solution for each index inversely with S in the middle to reduce the problem to ([1, 1, 1, …, X], ??). Where ?? is the result of applying all necessary F starting from the first index to reduce the hydra to a single stem.
