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 A372478 #33 May 09 2024 09:02:16 %S A372478 0,1,3,37 %N A372478 Number of steps required to kill a Kirby-Paris hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new subtrees sprout from the head's grandparent node (see comments). %C A372478 This is a variation of A372101 in which the hydra grows new subtrees instead of new heads. See Kirby and Paris (1982), p. 286, for a detailed explanation (with diagrams) of this process, for a generic hydra. %C A372478 Similar to A372101, the initial configuration of this specific hydra is a path with n segments. The rightmost head is the next to be chopped off. When this happens at step s, s new replicas of the subtree above the removed head's grandparent node (which includes the segment connecting the head's parent and grandparent) sprout to the right of the grandparent node. If the chopped head has no grandparent, no subtrees are added. %C A372478 As an example, here's how the following hypothetical portion of the hydra evolves, assuming we are at step 2 (H = head, o = node, X is chopped head, P = parent node, G = grandparent node): %C A372478 . %C A372478 H H H H H H H H %C A372478 \ | \ | | | | | %C A372478 o o X o o o o o o 2 new replicas (excluding the removed segment) %C A372478 \|/ \| |/ |/ of the subtree "above" (and including) the %C A372478 P ---> o o o G-P segment grow at the right of node G %C A372478 | |/ / %C A372478 H--o--G H--o--G---- %C A372478 | | %C A372478 . %C A372478 According to the Wikipedia article, a(4) >> Graham's number. %C A372478 In their paper, Kirby and Paris prove that no matter what the starting configuration of the hydra is--as long as it's a finite tree--and no matter which head is chosen to be chopped off next, the hydra will eventually be defeated. %C A372478 See A180368 for a variation in which only one new subtree grows after each chopping. %H A372478 Laurie Kirby and Jeff Paris, <a href="http://logic.amu.edu.pl/images/3/3c/Kirbyparis.pdf">Accessible Independence Results for Peano Arithmetic</a>, Bulletin of The London Mathematical Society, 14, 1982, pp. 285-293. %H A372478 PBS Infinite Series, <a href="https://www.youtube.com/watch?v=uWwUpEY4c8o">Kill the Mathematical Hydra</a>, YouTube video, 2017. %H A372478 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hydra_game">Hydra game</a>. %e A372478 In the following tree diagrams R is the root, o is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X. %e A372478 For n = 2, the sequence of the 3 choppings is: %e A372478 . %e A372478 H X %e A372478 \ \ %e A372478 o o H H X X %e A372478 \ \ / \ / \ %e A372478 R R R R %e A372478 . %e A372478 For n = 3, the sequence of the 37 choppings is: %e A372478 . %e A372478 H X %e A372478 \ \ %e A372478 o o H H X H H H H X H H %e A372478 \ \ / \| | / \ | / \ | %e A372478 o o o o o o o o H H H o o X X X X %e A372478 \ \ \|/ \|/ / / / \|/ / / / %e A372478 R R R R------ R------ %e A372478 . %e A372478 H X H X %e A372478 \ | \ \ %e A372478 o o H (8) H o X (9) X o H (18) H X (19) X %e A372478 \|/ ... / \ / ... / \ / ... / \ ... / %e A372478 R------ R------ R--------- ---R--- %e A372478 . %Y A372478 Cf. A180368, A372101, A372421. %Y A372478 Last element in each row of A372595. %K A372478 nonn,hard %O A372478 0,3 %A A372478 _Paolo Xausa_, May 02 2024