OFFSET
0,3
COMMENTS
To kill the hydra means to remove all of its heads, leaving only the root node.
New heads are created "to the right" of any existing head, i.e., they are now rightmost when considering which head to remove next.
The effect of this rule is that the next head to be removed is always any one of the heads closest to the root.
Please note that the a(4) value reported on the Numberphile link (983038) is wrong.
See the first Li link for the derivation of a(5), and which is hugely too big to display.
The problem can be phrased as follows. Start with a state S consisting of (v, s), where the vector v encodes the hydra and s is the next step number (if there is a next step). Initially, v starts with n ones and s = 1. At each iteration, do the following.
1. If v[1] = 1 and all other v[i] = 0 then the hydra is dead and a(n) = s-1.
2. Otherwise, find the least index i where v[i] >= 2, or if no such i then the greatest i where v[i] = 1.
3. Decrement v[i].
4. If i > 1 then increase v[i-1] by s.
5. Increase s by 1 and return to step 1.
See the first Corneth link for a step-by-step implementation of this procedure for a(3) and a(4).
LINKS
David A. Corneth, Calculation of a(3) and a(4).
David A. Corneth, PARI program.
Brady Haran and Tom Crawford, The Hydra Game, Numberphile YouTube video, 2024.
Calvin Li, hydra(5), 2024.
Calvin Li, The Hydra Game Solved, 2024.
Wikipedia, Hydra game.
FORMULA
a(3) = (2 + 1)*2^2 - 1 = (2*a(1) + 1)*(2^(a(1) + 1)) - 1 = 11.
a(4) = (2^2^2 + 1)*2^2^2^2 - 1 = (2^^a(2) + 1)*(2^^(a(2) + 1)) - 1 = 1114111, where ^^ is Knuth's double arrow notation (tetration).
For n >= 2, a(n) = F_1(F_2(...F_{n-1}(1))), where F_i(x) = (F_{i-1})^x (x+1) = F_{i-1}(F_{i-1}(...x times...(x+1))) and F_1(x) = 2*x + 1. See second Li link.
EXAMPLE
In the following tree diagrams R is the root, N is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X.
For n = 2, the sequence of the 3 choppings is:
.
H X
\ \
N N H H X X
\ \ / \ / \
R R R R
.
(0) (1) (2) (3)
.
Notes:
(0) The starting configuration of the hydra.
(1) The only head present is chopped off: one (because we are at step 1) new head grows from the root (the removed head's grandparent node), while the removed head's parent becomes a head.
(2) There are now two heads attached to the root: one of them is chopped off, and no new heads grow (no grandparent node).
(3) The remaining head is chopped off, leaving the root node: the hydra is killed.
.
For n = 3, the sequence of the 11 choppings is (the last 6 choppings are shown in a single diagram):
.
H X
\ \
N N H H X H H X
\ \ / \ / \ \ \
N N N H N H N X N H H X X X
\ \ \ / \ / \ / \|/ \|/
R R R--H R--X R R--H R--X
|\ |\
H H X X
.
(0) (1) (2) (3) (4) (5) (6)
.
Notes:
(0) The starting configuration of the hydra.
(1) The only head present is chopped off: one (because we are at step 1) new head grows from the removed head's grandparent node, while the removed head's parent becomes a head.
(2) There are now two heads at the same distance from the root: one of them is chopped off, and two (because we are at step 2) new heads grow from the root (the removed head's grandparent node).
(3) One of the two heads attached to the root is chopped off: no new heads grow (no grandparent node).
(4) The other head attached to the root is chopped off: no new heads grow (no grandparent node).
(5) The only head present is chopped off: five (because we are at step 5) new heads grow from the root (the removed head's grandparent node), while the removed head's parent becomes a head.
(6) There are now six heads connected to the root: each head is chopped off in turn, killing the hydra.
MATHEMATICA
A372101[n_] := Block[{h = PadLeft[{1}, n], s = 0, i},
While[Total[h] > 0,
If[h[[1]] > 0,
s += h[[1]]; h[[1]] = 0,
i = 1; While[h[[++i]] == 0];
If[h[[i]] == 1 && i == Length[h], h = Rest[h], h[[i]]--];
h[[i-1]] += ++s;
]]; s];
Array[A372101, 5, 0]
(* Second program, using Li's recursion *)
hydra[x_, i_] := If[i == 1, 2*x + 1, Nest[hydra[#, i - 1] &, x + 1, x]];
Join[{0}, Array[Fold[hydra, 1, Range[# - 1, 1, -1]] &, 4]]
PROG
(PARI) \\ See Links
CROSSREFS
KEYWORD
nonn,hard,nice
AUTHOR
Paolo Xausa and David A. Corneth, Apr 18 2024
STATUS
approved