%I #16 Jul 15 2023 06:20:56
%S 0,1,2,4,6,12,22,42,76,142,262,488,902,1674,3100,5750,10654,19752,
%T 36606,67858,125772,233134,432118,800968,1484630,2751866,5100732,
%U 9454534,17524526,32482792,60208782,111600642,206858476,383424702,710700742,1317326728,2441744422
%N Number of simple moves of the smallest disk in the solution to the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks.
%C 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.
%C Stockmeyer et al. show the shortest solution to the puzzle is f(n) = A341579(n) steps. They offer as an exercise for the reader to prove that the number of exchanges made within the solution is f(n-1) and the remaining a(n) = f(n) - f(n-1) here is the number of simple moves of the smallest disk (move-only, not exchange).
%H Kevin Ryde, <a href="/A341582/b341582.txt">Table of n, a(n) for n = 0..700</a>
%H Paul K. Stockmeyer et al., <a href="https://doi.org/10.1080/00207169508804452">Exchanging Disks in the Tower of Hanoi</a>, International Journal of Computer Mathematics, volume 59, number 1-2, pages 37-47, 1995. Also <a href="http://www.cs.wm.edu/~pkstoc/gov.pdf">author's copy</a>. See section 5 exercise 2.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,2).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F a(n) = A341579(n) - A341579(n-1), for n>=1. [Stockmeyer et al.]
%F a(n) = a(n-1) + a(n-2) + 2*a(n-4).
%F G.f.: x*(1 + x + x^2)/(1 - x - x^2 - 2*x^4)
%e 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.),
%e A
%e / \ n=3 disks
%e B---* solution
%e / \ A to H,
%e C * within
%e / \ / \ which
%e *---D---*---* a(3) = 4
%e / \ smallest
%e * / \ * disk moves:
%e / \ / \ / \ AB, CD,
%e F---E *---* EF, GH
%e / \ / \
%e G I-------* *
%e / \ / \ / \ / \
%e H---*---*---J *---*---*---*
%e For n=4, the first half of the solution is A to J per A341580. The smallest disk moves are AB, CD, IJ, and twice those is a(4) = 2*3 = 6 since J across to the next subgraph is an exchange, not a smallest disk move.
%t A341582list[nmax_]:=LinearRecurrence[{1,1,0,2},{0,1,2,4},nmax+1];A341582list[50] (* _Paolo Xausa_, Jun 29 2023 *)
%o (PARI) my(p=Mod('x,'x^4-'x^3-'x^2-2)); a(n) = subst(lift(p^n)\'x,'x,2);
%Y Cf. A341579, A341580.
%K nonn,easy
%O 0,3
%A _Kevin Ryde_, Feb 16 2021