|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(0) = 0; for n >= 1, a(n) = a(n-1)*(a(n-1)+1)/2 + n = A000217(a(n-1)) + n.
|
|
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
|
Last element in each row of A372593.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|