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.

0, 1, 3, 9, 49, 1230, 757071, 286578628063, 41063655031378934880024, 843111882268046256673111236649909091104560309, 355418823010783945962646271385485944012152784388172734299894340514265378207290093661367905

Offset: 0

Author

Paolo Xausa and Pontus von Brömssen, Apr 30 2024

Keywords

• nonn

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.

Examples

			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.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..13
• Wikipedia, Hydra game.

Crossrefs

Cf. A000217, A180368, A372101.

Partial sums of A370615.

Last element in each row of A372593.

Sequences with similar recurrences: A006894, A007501.

Programs

Mathematica

Block[{n = 0}, NestList[++n + PolygonalNumber[#] &, 0, 11]]

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