cp's OEIS Frontend

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

%I A180368 #30 May 09 2024 09:02:32
%S A180368 0,1,3,8,38,161915
%N A180368 Number of steps of the one-sided hydra process for a linear tree of length n.
%C A180368 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 A180368 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 A180368 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 A180368 (Note that in the myth, the Hydra had 9 heads, and each head that was chopped off was replaced by two smaller ones.)
%e A180368 Here is the sequence of hydra transformations for a(3) = 8.
%e A180368 Sequence of heights is     3,2,2,2,2,2,1,1,0.
%e A180368 Sequence of node counts is 4,4,5,5,4,3,3,2,1.
%e A180368 Sequence of head counts is 1,2,2,3,2,1,2,1,0.
%e A180368 x is the head that will be cut off at the next step:
%e A180368 x
%e A180368 |
%e A180368 o      x o      x o          o        o      x
%e A180368 |      |/       | |          |        |      |
%e A180368 o      o        o o      x o o      x o      o      x o      x
%e A180368 |      |        |/        \|/       |/       |      |/       |
%e A180368 o  =>  o    =>  o    =>    o    =>  o    =>  o  =>  o    =>  o  =>  o
%p A180368 b:= proc(h) local f; f:= h[1];
%p A180368        subsop(1=`if`(f=[], NULL,
%p A180368                 `if`(f[1]=[], (subsop(1=NULL, f))$2
%p A180368                              , b(f))), h)
%p A180368     end:
%p A180368 a:= proc(n) local i, t;
%p A180368       [];
%p A180368       for i to n do [%] od;
%p A180368       for t from 0 while %<>[] do b(%) od; t
%p A180368     end:
%p A180368 seq(a(n), n=0..5);  # _Alois P. Heinz_, Mar 31 2011
%Y A180368 Cf. A372101, A372421, A372478.
%Y A180368 Last element in each row of A372594.
%K A180368 nonn,more
%O A180368 0,3
%A A180368 _Vladimir Reshetnikov_, Aug 31 2010
%E A180368 Edited by _Olivier Gérard_, Mar 28 2011