cp's OEIS Frontend

A372421 Number of steps required to kill the hydra in a version of the hydra game (see comments) where the rightmost head is chopped off in each step and new heads are grown to the left.

%I A372421 #46 May 09 2024 08:03:49
%S A372421 0,1,3,9,49,1230,757071,286578628063,41063655031378934880024,
%T A372421 843111882268046256673111236649909091104560309,
%U A372421 355418823010783945962646271385485944012152784388172734299894340514265378207290093661367905
%N A372421 Number of steps required to kill the hydra in a version of the hydra game (see comments) where the rightmost head is chopped off in each step and new heads are grown to the left.
%C A372421 The hydra is represented as an ordered tree, initialized to a path with n edges, with the root of the tree at a terminal node of the path. At the k-th step, the leaf (head) that is reached by following the rightmost path from the root is chopped off (equivalently, for this specific hydra, the head to be chopped off is always one of the heads farthest from the root). If only the root remains, the hydra dies and the game ends. If the head chopped off was directly connected to the root, nothing more happens in this step. Otherwise, k new heads are grown from the node two levels closer to the root from the head chopped off (its grandparent).
%C A372421 In this version, the new heads grow to the left of all existing branches of the grandparent, while in A372101, they grow to the right.
%H A372421 Paolo Xausa, <a href="/A372421/b372421.txt">Table of n, a(n) for n = 0..13</a>
%H A372421 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hydra_game">Hydra game</a>.
%F A372421 a(0) = 0; for n >= 1, a(n) = a(n-1)*(a(n-1)+1)/2 + n = A000217(a(n-1)) + n.
%F A372421 a(n) ~ 2 * c^(2^n), where c = 1.2222440178780117503347646365410387156780573376846000146... - _Pontus von Brömssen_ and _Vaclav Kotesovec_, May 09 2024
%e A372421 For n = 3, the first three steps are illustrated in the diagrams below. In these diagrams, "R" denotes the root, "o" internal nodes, "X" the head to be chopped off, and "H" other heads.
%e A372421 .
%e A372421                      H       H H           H H H
%e A372421                     /        |/             \|/
%e A372421 R--o--o--X  =>  R--o--X  =>  R--o--X  =>  H--R--X
%e A372421                                             /
%e A372421                                            H
%e A372421 .
%e A372421 After this no more heads will grow, so another 6 steps are needed to chop off the remaining heads. The total number of steps is thus a(3) = 3 + 6 = 9.
%t A372421 Block[{n = 0}, NestList[++n + PolygonalNumber[#] &, 0, 11]]
%Y A372421 Cf. A000217, A180368, A372101.
%Y A372421 Partial sums of A370615.
%Y A372421 Last element in each row of A372593.
%Y A372421 Sequences with similar recurrences: A006894, A007501.
%K A372421 nonn
%O A372421 0,3
%A A372421 _Paolo Xausa_ and _Pontus von Brömssen_, Apr 30 2024