view release on metacpan or  search on metacpan

lib/Graph/Maker/HanoiExchange.pm  view on Meta::CPAN

37-47, 1995.  L<http://www.cs.wm.edu/~pkstoc/gov.pdf>.  See f(n) in
section 3.

=back

as recurrence

    f(N) = f(N-1) + f(N-2) + 2*f(N-4) + 3    for N>=4
         = 0, 1, 3, 7, 13, 25, 47, 89, 165, ...

This grows as a power r^N where r = 1.853... is the largest root of x^4 -
x^3 - x^2 - 2.  (Smaller than the plain Hanoi 2^N - 1.)

They consider also the geometric distance in a layout such as drawn above.
The resulting distance grows as 7/2*2^N.

=head1 OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to
this tree include

=over

L<http://oeis.org/A341579> (etc)

=back

    A341579    diameter

=cut

# GP-DEFINE  read("OEIS-data.gp");
# GP-DEFINE  read("OEIS-data-wip.gp");
# vector(10,n,f(n))
# not in OEIS: 1, 3, 7, 13, 25, 47, 89, 165, 307, 569
# abs(polroots(polrecip(1 - x - x^2 - 2*x^4)))
# not in OEIS: 1.8535602775

#------
# GP-DEFINE  read("memoize.gp");
# GP-DEFINE  f(n) = {
# GP-DEFINE    n>=0 || error();
# GP-DEFINE    if(n==0,0, n==1,1, n==2,3, n==3,7,
# GP-DEFINE       f(n-1) + f(n-2) + 2*f(n-4) + 3);
# GP-DEFINE  }
# GP-DEFINE  f=memoize(f);
# GP-DEFINE  A341579(n) = f(n);
# GP-DEFINE  gf(x) = (x + x^2 + x^3)/(1 - 2*x + x^3 - 2*x^4 + 2*x^5);
# GP-DEFINE  f_poly(x) = x^5 - 2*x^4 + x^2 - 2*x + 2;  \\ charpoly of f
# GP-Test  f_poly(x) == polrecip(denominator(gf(x)))
#
# GP-Test  OEIS_check_func("A341579")
#
# GP-Test-Last  /* Stockmeyer et al, f in terms of g equation (1) */ \
# GP-Test-Last  vector(100,n, f(n)) == \
# GP-Test-Last  vector(100,n, 2*g(n-1) + 1)
# GP-Test-Last  my(a=A341579); \
# GP-Test-Last  vector(100,n, a(n)) == \
# GP-Test-Last  vector(100,n, 2*A341580(n-1) + 1)
#
# GP-Test  /* Stockmeyer et al, and formula above */ \
# GP-Test  my(a=f); \
# GP-Test  vector(100,n,n+=3; a(n)) == \
# GP-Test  vector(100,n,n+=3; a(n-1) + a(n-2) + 2*a(n-4) + 3)
# GP-Test  vector(100,N,N+=3; f(N) == f(N-1) + f(N-2) + 2*f(N-4) + 3) == \
# GP-Test  vector(100,N,N+=3; 1)
#
# GP-Test  /* f full recurrence */ \
# GP-Test  my(a=f); \
# GP-Test  vector(100,n,n+=4; a(n)) == \
# GP-Test  vector(100,n,n+=4; 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5))
#
# GP-Test  gf(x) + O(x^100) == sum(n=0,100, f(n)*x^n)
# GP-Test  gf(x) == x*(1 + x + x^2) / ( (1-x) * (1 - x - x^2 - 2*x^4) )
# GP-Test  gf(x) == -1/(1-x) + (1 + x + x^2 + 2*x^3)/(1 - x - x^2 - 2*x^4)
#
# GP-Test  /* example */ \
# GP-Test  f(3) == 7
# GP-Test-Last  A341580(2) == 3
#
# GP-DEFINE  my(p=Mod('x,'x^4-'x^3-'x^2-2)); f_compact(n) = subst(lift(p^n),'x,2) - 1;
# GP-Test  vector(200,n,n--; f(n)) == \
# GP-Test  vector(200,n,n--; f_compact(n))

# f backwards: -5/4, -1, -1/2, 0, 0, 1, 3, 7, 13
# g backwards: -3/4, -1/2, -1/2, 0, 1, 3, 6
# d backwards: -1/2, -1/4, 0, 0, 1, 3, 8, 18
# vector(20,n,f(n))
# vector(20,n,n-=6; d_compact(n) - 7/2<<n)
# vector(20,n,(f(n)+1)/2)
# OEIS_recurrence_guess(vector(20,n,n--;f(n)))
# for(n=0,35,print1(f(n),",");if(n==18||n==28,print()))
# my(p=Mod(x,x^4 - x^3 - x^2 - 2)); \
# lindep([vector(20,n,n+=10;  2*d(n) - 7<<n), \
#         vector(20,n,n+=10;polcoeff(lift(p^n),3)),\
#         vector(20,n,n+=10;polcoeff(lift(x*p^n),3)),\
#         vector(20,n,n+=10;polcoeff(lift(x^2*p^n),3)),\
#         vector(20,n,n+=10;polcoeff(lift(x^3*p^n),3))])
# lindep([vector(20,n,n+=10; n-=2; d(n)*2 - 7<<n), \
#         vector(20,n,n+=10;polcoeff(lift(p^n),0)),\
#         vector(20,n,n+=10;polcoeff(lift(p^n),1)),\
#         vector(20,n,n+=10;polcoeff(lift(p^n),2)),\
#         vector(20,n,n+=10;polcoeff(lift(p^n),3))])

#------
# GP-DEFINE  \\ g = half of f
# GP-DEFINE  g(n) = n>=0 || error(); (f(n+1)-1)/2;
# GP-DEFINE  A341580(n) = g(n);
# GP-DEFINE  gg(x) = (gf(x)/x - 1/(1-x))/2;
# vector(20,n,n--; g(n))
# not in OEIS: 1, 3, 6, 12, 23, 44, 82, 153, 284, 528, 979, 1816, 3366
# OEIS_recurrence_guess(vector(20,n,n--;g(n)))
# for(n=0,35,print1(g(n),",");if(n==18||n==28,print()))
#
# GP-Test  OEIS_check_func("A341580")
#
# GP-Test-Last  /* Stockmeyer et al, g in terms of h equation (2) */ \
# GP-Test-Last  vector(100,n, g(n)) == \
# GP-Test-Last  vector(100,n, g(n-1) + h(n-1) + 1)
# GP-Test-Last  my(a=A341580); \
# GP-Test-Last  vector(100,n, a(n)) == \