|
%I #85 May 09 2024 09:02:46
%S 0,1,3,11,1114111
%N 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 To kill the hydra means to remove all of its heads, leaving only the root node.
%C 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 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 Please note that the a(4) value reported on the Numberphile link (983038) is wrong.
%C See the first Li link for the derivation of a(5), and which is hugely too big to display.
%C 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 1. If v[1] = 1 and all other v[i] = 0 then the hydra is dead and a(n) = s-1.
%C 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 3. Decrement v[i].
%C 4. If i > 1 then increase v[i-1] by s.
%C 5. Increase s by 1 and return to step 1.
%C See the first Corneth link for a step-by-step implementation of this procedure for a(3) and a(4).
%C 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 David A. Corneth, <a href="/A372101/a372101.png">Calculation of a(3) and a(4)</a>.
%H David A. Corneth, <a href="/A372101/a372101.gp.txt">PARI program</a>.
%H Brady Haran and Tom Crawford, <a href="https://www.youtube.com/watch?v=prURA1i8Qj4">The Hydra Game</a>, Numberphile YouTube video, 2024.
%H Calvin Li, <a href="https://li.cal.vin/p/hydra5">hydra(5)</a>, 2024.
%H Calvin Li, <a href="https://li.cal.vin/p/the-hydra-game-solved">The Hydra Game Solved</a>, 2024.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hydra_game">Hydra game</a>.
%F a(3) = (2 + 1)*2^2 - 1 = (2*a(1) + 1)*(2^(a(1) + 1)) - 1 = 11.
%F 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 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 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 For n = 2, the sequence of the 3 choppings is:
%e .
%e H X
%e \ \
%e N N H H X X
%e \ \ / \ / \
%e R R R R
%e .
%e (0) (1) (2) (3)
%e .
%e Notes:
%e (0) The starting configuration of the hydra.
%e (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 (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 (3) The remaining head is chopped off, leaving the root node: the hydra is killed.
%e .
%e For n = 3, the sequence of the 11 choppings is (the last 6 choppings are shown in a single diagram):
%e .
%e H X
%e \ \
%e N N H H X H H X
%e \ \ / \ / \ \ \
%e N N N H N H N X N H H X X X
%e \ \ \ / \ / \ / \|/ \|/
%e R R R--H R--X R R--H R--X
%e |\ |\
%e H H X X
%e .
%e (0) (1) (2) (3) (4) (5) (6)
%e .
%e Notes:
%e (0) The starting configuration of the hydra.
%e (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 (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 (3) One of the two heads attached to the root is chopped off: no new heads grow (no grandparent node).
%e (4) The other head attached to the root is chopped off: no new heads grow (no grandparent node).
%e (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 (6) There are now six heads connected to the root: each head is chopped off in turn, killing the hydra.
%t A372101[n_] := Block[{h = PadLeft[{1}, n], s = 0, i},
%t While[Total[h] > 0,
%t If[h[[1]] > 0,
%t s += h[[1]]; h[[1]] = 0,
%t i = 1; While[h[[++i]] == 0];
%t If[h[[i]] == 1 && i == Length[h], h = Rest[h], h[[i]]--];
%t h[[i-1]] += ++s;
%t ]]; s];
%t Array[A372101, 5, 0]
%t (* Second program, using Li's recursion *)
%t hydra[x_, i_] := If[i == 1, 2*x + 1, Nest[hydra[#, i - 1] &, x + 1, x]];
%t Join[{0}, Array[Fold[hydra, 1, Range[# - 1, 1, -1]] &, 4]]
%o (PARI) \\ See Links
%Y Cf. A180368, A372421, A372478.
%Y Last element in each row of A372592.
%K nonn,hard,nice
%O 0,3
%A _Paolo Xausa_ and _David A. Corneth_, Apr 18 2024
|