OFFSET
0,3
COMMENTS
Scorer, Grundy and Smith define a variation of the towers of Hanoi puzzle where the smallest disk moves freely and two disks can exchange positions when they differ in size by 1, are on different pegs, and each is topmost on its peg. The aim is to move a stack of n disks from one peg to another.
Stockmeyer et al. show that the number of steps in the solution is a(n), and that the sequence of steps is unique. They offer as exercises for the reader to prove that the number of exchanges with the solution is a(n-1), and that a(n) is the largest number of steps between any two configurations (in other words, a(n) is the diameter of the state graph).
LINKS
Kevin Ryde, Table of n, a(n) for n = 0..700
R. S. Scorer, P. M. Grundy, and C. A. B. Smith, Some Binary Games, The Mathematical Gazette, July 1944, volume 28, number 280, pages 96-103, section 4(iii) Plane Network Game.
Paul K. Stockmeyer, C. Douglass Bateman, James W. Clark, Cyrus R. Eyster, Matthew T. Harrison, Nicholas A. Loehr, Patrick J. Rodriguez, and Joseph R. Simmons III, Exchanging Disks in the Tower of Hanoi, International Journal of Computer Mathematics, volume 59, number 1-2, pages 37-47, 1995. Also author's copy. a(n) = f(n) in section 3.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-2).
FORMULA
a(n) = 2*A341580(n-1) + 1 for n>=1. [Stockmeyer et al.]
a(n) = a(n-1) + a(n-2) + 2*a(n-4) + 3 for n>=4. [Stockmeyer et al.]
a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - 2*a(n-5).
G.f.: x*(1 + x + x^2) / ( (1-x) * (1 - x - x^2 - 2*x^4) ).
G.f.: -1/(1-x) + (1 + x + x^2 + 2*x^3)/(1 - x - x^2 - 2*x^4).
EXAMPLE
As a graph where each vertex is a configuration of disks on pegs and each edge is a step (as drawn by Scorer et al.),
A
/ \
*---* n=3 disks
/ \ A to D
* * a(3) = 7 steps
/ \ / \
*---B---*---*
/ \
* / \ *
/ \ / \ / \
*---C *---*
/ \ / \
* *-------* *
/ \ / \ / \ / \
D---*---*---* *---*---*---*
MATHEMATICA
A341579list[nmax_]:=LinearRecurrence[{2, 0, -1, 2, -2}, {0, 1, 3, 7, 13}, nmax+1]; A341579list[50] (* Paolo Xausa, Jun 29 2023 *)
PROG
(PARI) my(p=Mod('x, 'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^n), 'x, 2) - 1;
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Feb 15 2021
STATUS
approved