OFFSET
0,3
COMMENTS
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).
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.
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..13
Wikipedia, Hydra game.
FORMULA
a(0) = 0; for n >= 1, a(n) = a(n-1)*(a(n-1)+1)/2 + n = A000217(a(n-1)) + n.
a(n) ~ 2 * c^(2^n), where c = 1.2222440178780117503347646365410387156780573376846000146... - Pontus von Brömssen and Vaclav Kotesovec, May 09 2024
EXAMPLE
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.
.
H H H H H H
/ |/ \|/
R--o--o--X => R--o--X => R--o--X => H--R--X
/
H
.
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.
MATHEMATICA
Block[{n = 0}, NestList[++n + PolygonalNumber[#] &, 0, 11]]
CROSSREFS
KEYWORD
nonn
AUTHOR
Paolo Xausa and Pontus von Brömssen, Apr 30 2024
STATUS
approved