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

0, 1, 3, 8, 38, 161915

Offset: 0

Author

Vladimir Reshetnikov, Aug 31 2010

Keywords

• nonn
• more

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