A372593 -id:A372593 - cp's OEIS frontend

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

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

nonn

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.

			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.

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

Cf. A000217, A180368, A372101.
Partial sums of A370615.
Last element in each row of A372593.
Sequences with similar recurrences: A006894, A007501.

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

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

A372592 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 right.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 7, 11, 4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111, 5, 6, 7, 9, 13, 8, 10, 12, 16, 24, 32, 80, 448, 1114112, 9, 11, 13, 17, 25, 15, 19, 23, 31, 47, 63, 159, 895, 2228223, 79, 191, 447, 2303, 53247, 1114111, 45079976738815, 6065988000108893953800078394579416901568357495071628808248312306073599

Offset: 0

Pontus von Brömssen, May 06 2024

As in A372101, 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 right of all existing branches of that node.

T(5,37) = 20472...84351 (167697 digits). The corresponding initial tree is represented by the bracket string "((()(())))" (the 37th Dyck word on 5 pairs of brackets).

			Triangle begins:
  0;
  1;
  2, 3;
  3, 4, 5, 7, 11;
  4, 5, 6, 8, 12, 7, 9, 11, 15, 23, 31, 79, 447, 1114111;
  ...
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". 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       H   H       H   X      X
   \ /           \ /         \ /         \ /        \
    o             o--X        o H         o          o      X
    |             |           |/          |          |      |
    R       =>    R     =>    R--X  =>    R    =>    R  =>  R  =>  R
  T(4,10) = 1     +     1     +     2     +    6     +  12  +  1   = 23.

Last elements on each row give A372101.

Cf. A000108, A063171, A372593, A372594, A372595.

T(n,k) = T(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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A372592 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 right.

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