login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180368 Number of steps of the one-sided hydra process for a linear tree of length n. 0
0, 1, 3, 8, 38, 161915 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This process on trees is called Hydra in reference to Hercules myth (2nd work).

When you cut a head (leaf node), a node that was its parent replicates together with a remaining subtree (unless the parent was the root node). It ends when there is only the root node.

Given a linear hydra of length n, how many heads do you have to cut if you always cut the leftmost remaining head?

(Note that in the myth, Hydra had 9 heads and chopped heads were replaced by two smaller ones.)

LINKS

Table of n, a(n) for n=0..5.

EXAMPLE

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

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

CROSSREFS

Sequence in context: A106558 A065914 A288759 * A108262 A034892 A072687

Adjacent sequences:  A180365 A180366 A180367 * A180369 A180370 A180371

KEYWORD

nonn,more

AUTHOR

Vladimir Reshetnikov, Aug 31 2010

EXTENSIONS

Edited by Olivier Gérard, Mar 28 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 6 15:23 EDT 2020. Contains 333276 sequences. (Running on oeis4.)