A372592 -id:A372592 - cp's OEIS frontend

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).

0, 1, 3, 11, 1114111

Offset: 0

Paolo Xausa and David A. Corneth, Apr 18 2024

To kill the hydra means to remove all of its heads, leaving only the root node.
New heads are created "to the right" of any existing head, i.e., they are now rightmost when considering which head to remove next.
The effect of this rule is that the next head to be removed is always any one of the heads closest to the root.
Please note that the a(4) value reported on the Numberphile link (983038) is wrong.
See the first Li link for the derivation of a(5), and which is hugely too big to display.
The problem can be phrased as follows. Start with a state S consisting of (v, s), where the vector v encodes the hydra and s is the next step number (if there is a next step). Initially, v starts with n ones and s = 1. At each iteration, do the following.
1. If v[1] = 1 and all other v[i] = 0 then the hydra is dead and a(n) = s-1.
2. Otherwise, find the least index i where v[i] >= 2, or if no such i then the greatest i where v[i] = 1.
3. Decrement v[i].
4. If i > 1 then increase v[i-1] by s.
5. Increase s by 1 and return to step 1.
See the first Corneth link for a step-by-step implementation of this procedure for a(3) and a(4).
A372421 is a variation where new heads grow to the left of all existing heads, while in A372478 subtrees grow instead of just heads.

			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.

Cf. A180368, A372421, A372478.

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]]

PARI
```
\\ See Links
```

a(3) = (2 + 1)*2^2 - 1 = (2*a(1) + 1)*(2^(a(1) + 1)) - 1 = 11.
a(4) = (2^2^2 + 1)*2^2^2^2 - 1 = (2^^a(2) + 1)*(2^^(a(2) + 1)) - 1 = 1114111, where ^^ is Knuth's double arrow notation (tetration).
For n >= 2, a(n) = F_1(F_2(...F_{n-1}(1))), where F_i(x) = (F_{i-1})^x (x+1) = F_{i-1}(F_{i-1}(...x times...(x+1))) and F_1(x) = 2*x + 1. See second Li link.

A372593 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game 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) and new heads are grown to the left.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 9, 4, 5, 6, 7, 10, 7, 8, 9, 10, 14, 18, 19, 25, 49, 5, 6, 7, 8, 11, 8, 9, 10, 11, 15, 19, 20, 26, 50, 9, 10, 11, 12, 16, 12, 13, 14, 15, 20, 25, 26, 33, 60, 30, 31, 32, 33, 41, 49, 50, 60, 110, 175, 176, 195, 330, 1230

Offset: 0

Pontus von Brömssen, May 06 2024

As in A372421, the rightmost head (leaf) is always chopped off, and after the m-th head is chopped off (if it is not directly connected to the root) m new heads grow from the node two levels closer to the root from the head chopped off (its grandparent) to the left of all existing branches of that node.
For a given initial ordered tree T, the number of steps in the hydra game can be found by the following algorithm. The algorithm finds h(T,m0), the number of steps in a generalization of the game for an ordered tree T, with m0 new heads growing out at the first step (and, as before, increasing by one at each subsequent step). (So A(n,k) = h(T,1) if T is the k-th tree with n edges.)
  1. If the root is the only node of T, return 0.
  2. Set m = m0 and c = n - m*(m-1)/2, where n is the number of edges of T.
  3. Delete the root from T. For each of the resulting tree components T' (from right to left), rooted at the node that was connected to the root of T:
    a. Set m = m + h(T',m) + 1.
    b. If T' is not the last tree, set c = c-m+1.
  4. Return c + (m-1)*(m-2)/2.

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 6,  9;
  4, 5, 6, 7, 10, 7, 8, 9, 10, 14, 18, 19, 25, 49;
  ...
For n = 4, k = 10, the hydra game for the initial tree corresponding to the bracket string "(()(()))" (the 10th Dyck word on 4 pairs of brackets) is shown below. The root is denoted by "R", internal nodes by "o", the head to be chopped off by "X", other heads by "H". A number connected to the root represents that number of leaves, each connected to the root. 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.
.
      X
     /
  H o           H H X       H X       X
  |/             \|/         \|        \
  o               o         H o         o         X
  |               |          \|         |         |
  R         =>    R    =>  H--R  =>  5--R  =>  9--R  =>  R
  A(4,10) = 1     +    1      +  1      +  1      +  10  = 14.

Last elements on each row give A372421.

Cf. A000108, A063171, A372592, A372594, A372595.

A(n,k) = A(n-1,k)+1 if 1 <= k <= A000108(n-1).

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

Pontus von Brömssen, May 06 2024

Here, in contrast to A180368, the rightmost head is always chopped off. Equivalently, chop off the leftmost head but interpret the Dyck words as describing the trees from the right to the left (or sort the Dyck words colexicographically).

			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.

Cf. A000108, A063171, A372592, A372593, A372595.

T(n,k) = T(n-1,k)+1 if 1 <= k <= A000108(n-1).

A372595 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game (the version described in A372478) 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, 5, 13, 37, 4, 5, 6, 14, 38, 7, 9, 37, 22539988369405

Offset: 0

Pontus von Brömssen, May 06 2024

T(4,9) = 41*2^39 - 3 = 22539988369405.

T(4,10) = (97*2^95+1)*2^(97*2^95-1) - 3 (1156727590779508264240712695467 digits).

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 13, 37;
  4, 5, 6, 14, 38, 7, 9, 37, 22539988369405, ...;
  ...

Last elements on each row give A372478.

Cf. A000108, A063171, A372592, A372593, A372594.

T(n,k) = T(n-1,k)+1 if 1 <= k <= A000108(n-1).

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A372593 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game 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) and new heads are grown to the left.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A372595 Irregular triangle read by rows, where the n-th row gives the number of steps in the hydra game (the version described in A372478) 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).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula