A060590 Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.
0, 2, 2, 14, 10, 62, 42, 254, 170, 1022, 682, 4094, 2730, 16382, 10922, 65534, 43690, 262142, 174762, 1048574, 699050, 4194302, 2796202, 16777214, 11184810, 67108862, 44739242, 268435454, 178956970, 1073741822, 715827882, 4294967294
Offset: 0
Examples
a(2)=2 since there are nine equally likely possibilities, with times required of 0,1,1,2,2,3,3,3,3 giving an average of 18/9 = 2/1.
Links
- Harry J. Smith, Table of n, a(n) for n = 0..500
- Index entries for linear recurrences with constant coefficients, signature (0,5,0,-4).
- Index entries for sequences related to Towers of Hanoi
Programs
-
PARI
a(n)={2*(2^n - 1)*(2 - (-1)^n)/3} \\ Harry J. Smith, Jul 07 2009
Formula
a(n) = 2*(2^n - 1)*(2 - (-1)^n)/3.
a(2n) = A020988(n-1).
From Ralf Stephan, Mar 07 2003: (Start)
G.f.: (4*x^3+2*x^2+2*x)/(4*x^4-5*x^2+1).
a(n+4) = 5*a(n+2) - 4*a(n). (End)