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 puzzle is to move a stack of n disks from one peg to another.
Stockmeyer et al. determine the shortest solution to the puzzle. a(n) is their h(n) which is the number of steps to go from n disks on peg X to the largest disk to peg Y and the others remaining on X. This arises in A341580 to go between subgraph "connection" points.
LINKS
Kevin Ryde, Table of n, a(n) for n = 0..700
Paul K. Stockmeyer et al., 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) = h(n) in section 3.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-2).
FORMULA
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
* * steps
/ \ / \ a(3) = 5
*---B---*---*
/ \
D / \ *
/ \ / \ / \
*---C *---*
/ \ / \
* *-------* *
/ \ / \ / \ / \
*---*---*---* *---*---*---*
PROG
(PARI) my(p=Mod('x, 'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^(n+2))\'x, 'x, 2)/2 - 1;
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Kevin Ryde, Feb 16 2021
STATUS
approved