A372101 Number of steps required to kill a hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new heads grow to the right of the head's grandparent node (see comments).

0, 1, 3, 11, 1114111

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).

A372421 is a variation where new heads grow to the left of all existing heads, while in A372478 subtrees grow instead of just heads.

Links

Table of n, a(n) for n=0..4.

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

Cf. A180368, A372421, A372478.

Last element in each row of A372592.

Sequence in context: A212814 A101710 A088799 * A181405 A354568 A072117

Adjacent sequences: A372098 A372099 A372100 * A372102 A372103 A372104

Keyword

nonn,hard,nice

Author

Paolo Xausa and David A. Corneth, Apr 18 2024

Status

approved