A372421 -id:A372421 - 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.

A180368 Number of steps of the one-sided hydra process for a linear tree of length n.

Original entry on oeis.org

0, 1, 3, 8, 38, 161915

Offset: 0

Vladimir Reshetnikov, Aug 31 2010

This process on trees is called Hydra in reference to the Hercules myth (killing the Hydra was the 2nd of the 12 labors of Hercules).
When you cut off a head (leaf node), the node that was its parent replicates together with a remaining subtree (unless the parent was the root node). The process ends when there is only the root node.
Given a linear hydra of length n, how many heads do you have to cut off if you always cut off the leftmost remaining head?
(Note that in the myth, the Hydra had 9 heads, and each head that was chopped off was replaced by two smaller ones.)

			Here is the sequence of hydra transformations for a(3) = 8.
Sequence of heights is     3,2,2,2,2,2,1,1,0.
Sequence of node counts is 4,4,5,5,4,3,3,2,1.
Sequence of head counts is 1,2,2,3,2,1,2,1,0.
x is the head that will be cut off at the next step:
x
|
o      x o      x o          o        o      x
|      |/       | |          |        |      |
o      o        o o      x o o      x o      o      x o      x
|      |        |/        \|/       |/       |      |/       |
o  =>  o    =>  o    =>    o    =>  o    =>  o  =>  o    =>  o  =>  o

Cf. A372101, A372421, A372478.

Last element in each row of A372594.

b:= proc(h) local f; f:= h[1];
       subsop(1=`if`(f=[], NULL,
                `if`(f[1]=[], (subsop(1=NULL, f))$2
                             , b(f))), h)
    end:
a:= proc(n) local i, t;
      [];
      for i to n do [%] od;
      for t from 0 while %<>[] do b(%) od; t
    end:
seq(a(n), n=0..5);  # Alois P. Heinz, Mar 31 2011

Edited by Olivier Gérard, Mar 28 2011

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

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

0, 1, 3, 37

Offset: 0

Paolo Xausa, May 02 2024

This is a variation of A372101 in which the hydra grows new subtrees instead of new heads. See Kirby and Paris (1982), p. 286, for a detailed explanation (with diagrams) of this process, for a generic hydra.
Similar to A372101, the initial configuration of this specific hydra is a path with n segments. The rightmost head is the next to be chopped off. When this happens at step s, s new replicas of the subtree above the removed head's grandparent node (which includes the segment connecting the head's parent and grandparent) sprout to the right of the grandparent node. If the chopped head has no grandparent, no subtrees are added.
As an example, here's how the following hypothetical portion of the hydra evolves, assuming we are at step 2 (H = head, o = node, X is chopped head, P = parent node, G = grandparent node):
.
  H   H        H   H H H H H
   \  |         \  | | | | |
    o o X        o o o o o o   2 new replicas (excluding the removed segment)
     \|/          \| |/  |/    of the subtree "above" (and including) the
      P    --->    o o   o     G-P segment grow at the right of node G
      |            |/   /
H--o--G      H--o--G----
      |            |
.
According to the Wikipedia article, a(4) >> Graham's number.
In their paper, Kirby and Paris prove that no matter what the starting configuration of the hydra is--as long as it's a finite tree--and no matter which head is chosen to be chopped off next, the hydra will eventually be defeated.
See A180368 for a variation in which only one new subtree grows after each chopping.

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

Laurie Kirby and Jeff Paris, Accessible Independence Results for Peano Arithmetic, Bulletin of The London Mathematical Society, 14, 1982, pp. 285-293.
PBS Infinite Series, Kill the Mathematical Hydra, YouTube video, 2017.
Wikipedia, Hydra game.

Cf. A180368, A372101, A372421.

Last element in each row of A372595.

A370615 a(0) = 0. For n >= 1, a(n) = 1 + (sum of the next consecutive a(n-1) positive integers).

Original entry on oeis.org

0, 1, 2, 6, 40, 1181, 755841, 286577870992, 41063655031092356251961, 843111882268046256673070172994877712169680285, 355418823010783945962646271385485944012152783545060852031848083841154141557381002556807596

Offset: 0

Paolo Xausa, Apr 30 2024

nonn

			0, 0+1 = 1, 1+1 = 2, 2+3+1 = 6, 4+5+...+9+1 = 40, 10+11+...+49+1 = 1181, ...
   |        |        \_/        \_______/         \__________/
0 terms  1 term    2 terms       6 terms            40 terms

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

Partial sums give A372421.

Block[{k = 0}, Differences[NestList[PolygonalNumber[#] + k++ &, 0, 12]]]

a(0) = 0. For n >= 1, a(n) = A372421(n) - A372421(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

A180368 Number of steps of the one-sided hydra process for a linear tree of length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A370615 a(0) = 0. For n >= 1, a(n) = 1 + (sum of the next consecutive a(n-1) positive integers).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula