A291876 Consider the graph with one central vertex connected to three outer vertices (a star graph). Then, a(n) is the minimum number of moves required to transfer a stack of n pegs from one outer vertex to another outer vertex, moving pegs to adjacent vertices, following the rules of the Towers of Hanoi.

2, 6, 12, 20, 32, 48, 66, 90, 122, 158, 206, 260, 324, 396, 492, 600, 728, 872, 1034, 1226, 1442, 1698, 1986, 2310, 2694, 3126, 3612, 4124, 4700, 5348, 6116, 6980, 7952, 8976, 10128, 11424, 12882, 14418, 16146, 18090, 20138, 22442, 25034, 27950, 31022, 34478, 38366

Offset: 1

Author

Eric M. Schmidt, Sep 04 2017

Keywords

• nonn

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Thierry Bousch, La Tour de Stockmeyer, Séminaire Lotharingien de Combinatoire 77 (2017), Article B77d.
• Caroline Holz auf der Heide, Distances and automatic sequences in distinguished variants of Hanoi graphs, Dissertation. Fakultät für Mathematik, Informatik und Statistik. Ludwig-Maximilians-Universität München, 2016. [See Chapter 3.]
• Paul K. Stockmeyer, Variations on the Four-Post Tower of Hanoi Puzzle, Congr. Numer., 102 (1994), pp. 3-12.
• Eric Weisstein's World of Mathematics, Star Graph
• Index entries for sequences related to Towers of Hanoi

Crossrefs

Cf. A259823, A291877.

Programs

Maple

A[0]:= 0:
A[1]:= 2:
for n from 2 to 100 do A[n]:= min(seq(3*A[k]+2^(n-k+1)-2, k=0..n-1)) od:
seq(A[i],i=1..100); # Robert Israel, Oct 27 2017

Formula

Conjecturally, a(n) = 2*A259823(n).

This conjecture was proved by Thierry Bousch, see link. - Paul Zimmermann, Oct 05 2015

Extensions

Terms a(17) and beyond from Robert Israel, Oct 27 2017