A372594
Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game (the version described in A180368) when the initial hydra is each of the A000108(n) ordered trees with n edges (ordered by lexicographic order of their corresponding Dyck words as in A063171).
Original entry on oeis.org
0, 1, 2, 3, 3, 4, 4, 7, 8, 4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38, 5, 6, 6, 9, 10, 6, 7, 9, 16, 17, 10, 18, 38, 39, 6, 7, 7, 10, 11, 9, 10, 16, 31, 32, 17, 33, 69, 70, 10, 11, 18, 35, 36, 38, 75, 614, 615, 39, 77, 631, 161914, 161915
Offset: 0
Triangle begins:
0;
1;
2, 3;
3, 4, 4, 7, 8;
4, 5, 5, 8, 9, 5, 6, 8, 15, 16, 9, 17, 37, 38;
...
In the examples below, the hydra games for some initial trees are shown. The root is denoted by "R", internal nodes by "o", the head to be chopped off by "X", other heads by "H". Numbers below the arrows show how many steps that are required to go from the tree on the left to the tree on the right.
(n,k) = (2,2), corresponding to the 2nd Dyck word on 2 pairs of brackets, "(())":
X
|
o H X X
| |/ |
R => R => R => R
T(2,2) = 1 + 1 + 1 = 3.
.
(n,k) = (3,4), corresponding to the 4th Dyck word on 3 pairs of brackets, "(()())":
H X H X
\ / \ /
o o o
\ \ /
R => R => R
T(3,4) = 1 + 2*T(2,2) = 7.
.
(n,k) = (4,10), corresponding to the 10th Dyck word on 4 pairs of brackets, "(()(()))":
X
|
o H X H H
| |/ | |
H--o H--o H--o o--X
\ \ \ /
R => R => R => R
T(4,10) = 1 + 1 + 2*T(3,4) = 16.
Last elements on each row give
A180368.
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.
Original entry on oeis.org
0, 1, 3, 9, 49, 1230, 757071, 286578628063, 41063655031378934880024, 843111882268046256673111236649909091104560309, 355418823010783945962646271385485944012152784388172734299894340514265378207290093661367905
Offset: 0
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.
Last element in each row of
A372593.
A372101
Number of steps required to kill a hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new heads grow to the right of the head's grandparent node (see comments).
Original entry on oeis.org
0, 1, 3, 11, 1114111
Offset: 0
In the following tree diagrams R is the root, N is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X.
For n = 2, the sequence of the 3 choppings is:
.
H X
\ \
N N H H X X
\ \ / \ / \
R R R R
.
(0) (1) (2) (3)
.
Notes:
(0) The starting configuration of the hydra.
(1) The only head present is chopped off: one (because we are at step 1) new head grows from the root (the removed head's grandparent node), while the removed head's parent becomes a head.
(2) There are now two heads attached to the root: one of them is chopped off, and no new heads grow (no grandparent node).
(3) The remaining head is chopped off, leaving the root node: the hydra is killed.
.
For n = 3, the sequence of the 11 choppings is (the last 6 choppings are shown in a single diagram):
.
H X
\ \
N N H H X H H X
\ \ / \ / \ \ \
N N N H N H N X N H H X X X
\ \ \ / \ / \ / \|/ \|/
R R R--H R--X R R--H R--X
|\ |\
H H X X
.
(0) (1) (2) (3) (4) (5) (6)
.
Notes:
(0) The starting configuration of the hydra.
(1) The only head present is chopped off: one (because we are at step 1) new head grows from the removed head's grandparent node, while the removed head's parent becomes a head.
(2) There are now two heads at the same distance from the root: one of them is chopped off, and two (because we are at step 2) new heads grow from the root (the removed head's grandparent node).
(3) One of the two heads attached to the root is chopped off: no new heads grow (no grandparent node).
(4) The other head attached to the root is chopped off: no new heads grow (no grandparent node).
(5) The only head present is chopped off: five (because we are at step 5) new heads grow from the root (the removed head's grandparent node), while the removed head's parent becomes a head.
(6) There are now six heads connected to the root: each head is chopped off in turn, killing the hydra.
- David A. Corneth, Calculation of a(3) and a(4).
- David A. Corneth, PARI program.
- Brady Haran and Tom Crawford, The Hydra Game, Numberphile YouTube video, 2024.
- Calvin Li, hydra(5), 2024.
- Calvin Li, The Hydra Game Solved, 2024.
- Wikipedia, Hydra game.
Last element in each row of
A372592.
-
A372101[n_] := Block[{h = PadLeft[{1}, n], s = 0, i},
While[Total[h] > 0,
If[h[[1]] > 0,
s += h[[1]]; h[[1]] = 0,
i = 1; While[h[[++i]] == 0];
If[h[[i]] == 1 && i == Length[h], h = Rest[h], h[[i]]--];
h[[i-1]] += ++s;
]]; s];
Array[A372101, 5, 0]
(* Second program, using Li's recursion *)
hydra[x_, i_] := If[i == 1, 2*x + 1, Nest[hydra[#, i - 1] &, x + 1, x]];
Join[{0}, Array[Fold[hydra, 1, Range[# - 1, 1, -1]] &, 4]]
-
\\ See Links
A372478
Number of steps required to kill a Kirby-Paris hydra composed of a linear graph with n edges where, after removing the rightmost head at step s, s new subtrees sprout from the head's grandparent node (see comments).
Original entry on oeis.org
In the following tree diagrams R is the root, o is a node and H is a head (leaf). Head chopping (leaf removal) is denoted by X.
For n = 2, the sequence of the 3 choppings is:
.
H X
\ \
o o H H X X
\ \ / \ / \
R R R R
.
For n = 3, the sequence of the 37 choppings is:
.
H X
\ \
o o H H X H H H H X H H
\ \ / \| | / \ | / \ |
o o o o o o o o H H H o o X X X X
\ \ \|/ \|/ / / / \|/ / / /
R R R R------ R------
.
H X H X
\ | \ \
o o H (8) H o X (9) X o H (18) H X (19) X
\|/ ... / \ / ... / \ / ... / \ ... /
R------ R------ R--------- ---R---
.
Last element in each row of
A372595.
Showing 1-4 of 4 results.
Comments