This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A372101 #89 Jun 30 2025 09:57:50
%S A372101 0,1,3,11,1114111
%N 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).
%C A372101 To kill the hydra means to remove all of its heads, leaving only the root node.
%C A372101 New heads are created "to the right" of any existing head, i.e., they are now rightmost when considering which head to remove next.
%C A372101 The effect of this rule is that the next head to be removed is always any one of the heads closest to the root.
%C A372101 Please note that the a(4) value reported on the Numberphile link (983038) is wrong.
%C A372101 See the first Li link for the derivation of a(5), and which is hugely too big to display.
%C A372101 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.
%C A372101 1. If v[1] = 1 and all other v[i] = 0 then the hydra is dead and a(n) = s-1.
%C A372101 2. Otherwise, find the least index i where v[i] >= 2, or if no such i then the greatest i where v[i] = 1.
%C A372101 3. Decrement v[i].
%C A372101 4. If i > 1 then increase v[i-1] by s.
%C A372101 5. Increase s by 1 and return to step 1.
%C A372101 See the first Corneth link for a step-by-step implementation of this procedure for a(3) and a(4).
%C A372101 A372421 is a variation where new heads grow to the left of all existing heads, while in A372478 subtrees grow instead of just heads.
%H A372101 David A. Corneth, <a href="/A372101/a372101.png">Calculation of a(3) and a(4)</a>.
%H A372101 David A. Corneth, <a href="/A372101/a372101.gp.txt">PARI program</a>.
%H A372101 Brady Haran and Tom Crawford, <a href="https://www.youtube.com/watch?v=prURA1i8Qj4">The Hydra Game</a>, Numberphile YouTube video, 2024.
%H A372101 Calvin Li, <a href="https://blog.cal.vin/p/hydra5">hydra(5)</a>, 2024.
%H A372101 Calvin Li, <a href="https://blog.cal.vin/p/the-hydra-game-solved">The Hydra Game Solved</a>, 2024.
%H A372101 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hydra_game">Hydra game</a>.
%F A372101 a(3) = (2 + 1)*2^2 - 1 = (2*a(1) + 1)*(2^(a(1) + 1)) - 1 = 11.
%F A372101 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).
%F A372101 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.
%e A372101 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.
%e A372101 For n = 2, the sequence of the 3 choppings is:
%e A372101 .
%e A372101 H X
%e A372101 \ \
%e A372101 N N H H X X
%e A372101 \ \ / \ / \
%e A372101 R R R R
%e A372101 .
%e A372101 (0) (1) (2) (3)
%e A372101 .
%e A372101 Notes:
%e A372101 (0) The starting configuration of the hydra.
%e A372101 (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.
%e A372101 (2) There are now two heads attached to the root: one of them is chopped off, and no new heads grow (no grandparent node).
%e A372101 (3) The remaining head is chopped off, leaving the root node: the hydra is killed.
%e A372101 .
%e A372101 For n = 3, the sequence of the 11 choppings is (the last 6 choppings are shown in a single diagram):
%e A372101 .
%e A372101 H X
%e A372101 \ \
%e A372101 N N H H X H H X
%e A372101 \ \ / \ / \ \ \
%e A372101 N N N H N H N X N H H X X X
%e A372101 \ \ \ / \ / \ / \|/ \|/
%e A372101 R R R--H R--X R R--H R--X
%e A372101 |\ |\
%e A372101 H H X X
%e A372101 .
%e A372101 (0) (1) (2) (3) (4) (5) (6)
%e A372101 .
%e A372101 Notes:
%e A372101 (0) The starting configuration of the hydra.
%e A372101 (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.
%e A372101 (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).
%e A372101 (3) One of the two heads attached to the root is chopped off: no new heads grow (no grandparent node).
%e A372101 (4) The other head attached to the root is chopped off: no new heads grow (no grandparent node).
%e A372101 (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.
%e A372101 (6) There are now six heads connected to the root: each head is chopped off in turn, killing the hydra.
%t A372101 A372101[n_] := Block[{h = PadLeft[{1}, n], s = 0, i},
%t A372101 While[Total[h] > 0,
%t A372101 If[h[[1]] > 0,
%t A372101 s += h[[1]]; h[[1]] = 0,
%t A372101 i = 1; While[h[[++i]] == 0];
%t A372101 If[h[[i]] == 1 && i == Length[h], h = Rest[h], h[[i]]--];
%t A372101 h[[i-1]] += ++s;
%t A372101 ]]; s];
%t A372101 Array[A372101, 5, 0]
%t A372101 (* Second program, using Li's recursion *)
%t A372101 hydra[x_, i_] := If[i == 1, 2*x + 1, Nest[hydra[#, i - 1] &, x + 1, x]];
%t A372101 Join[{0}, Array[Fold[hydra, 1, Range[# - 1, 1, -1]] &, 4]]
%o A372101 (PARI) \\ See Links
%Y A372101 Cf. A180368, A372421, A372478.
%Y A372101 Last element in each row of A372592.
%K A372101 nonn,hard,nice
%O A372101 0,3
%A A372101 _Paolo Xausa_ and _David A. Corneth_, Apr 18 2024