cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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

Views

Author

Pontus von Brömssen, May 06 2024

Keywords

Comments

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

Examples

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

Crossrefs

Last elements on each row give A372478.
Cf. A000108, A063171, A372592, A372593, A372594.

Formula

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

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

Views

Author

Paolo Xausa and David A. Corneth, Apr 18 2024

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

Cf. A180368, A372421, A372478.
Last element in each row of A372592.

Programs

  • Mathematica
    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

Formula

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

Views

Author

Vladimir Reshetnikov, Aug 31 2010

Keywords

Comments

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

Examples

			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

Crossrefs

Cf. A372101, A372421, A372478.
Last element in each row of A372594.

Programs

  • Maple
    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

Extensions

Edited by Olivier Gérard, Mar 28 2011
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.