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

%I #30 May 09 2024 09:02:32

%S 0,1,3,8,38,161915

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

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

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

%C 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?

%C (Note that in the myth, the Hydra had 9 heads, and each head that was chopped off was replaced by two smaller ones.)

%e Here is the sequence of hydra transformations for a(3) = 8.

%e Sequence of heights is 3,2,2,2,2,2,1,1,0.

%e Sequence of node counts is 4,4,5,5,4,3,3,2,1.

%e Sequence of head counts is 1,2,2,3,2,1,2,1,0.

%e x is the head that will be cut off at the next step:

%e x

%e |

%e o x o x o o o x

%e | |/ | | | | |

%e o o o o x o o x o o x o x

%e | | |/ \|/ |/ | |/ |

%e o => o => o => o => o => o => o => o => o

%p b:= proc(h) local f; f:= h[1];

%p subsop(1=`if`(f=[], NULL,

%p `if`(f[1]=[], (subsop(1=NULL, f))$2

%p , b(f))), h)

%p end:

%p a:= proc(n) local i, t;

%p [];

%p for i to n do [%] od;

%p for t from 0 while %<>[] do b(%) od; t

%p end:

%p seq(a(n), n=0..5); # _Alois P. Heinz_, Mar 31 2011

%Y Cf. A372101, A372421, A372478.

%Y Last element in each row of A372594.

%K nonn,more

%O 0,3

%A _Vladimir Reshetnikov_, Aug 31 2010

%E Edited by _Olivier GĂ©rard_, Mar 28 2011