login
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.
6
0, 1, 3, 9, 49, 1230, 757071, 286578628063, 41063655031378934880024, 843111882268046256673111236649909091104560309, 355418823010783945962646271385485944012152784388172734299894340514265378207290093661367905
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
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
Partial sums of A370615.
Last element in each row of A372593.
Sequences with similar recurrences: A006894, A007501.
Sequence in context: A356270 A190009 A012063 * A036751 A260156 A058110
KEYWORD
nonn
AUTHOR
STATUS
approved