On generalized Frame-Stewart numbers

Abstract: For the multi-peg Tower of Hanoi problem with

k g e q s l a n t 4

pegs, so far the best solution is obtained by the Stewart's algorithm based on the the following recurrence relation:

m a t h r m S_{k} (n) = m i n_{1 l e q s l a n t t l e q s l a n t n} l e f t 2 c d o t m a t h r m S_{k} (n - t) + m a t h r m S_{k - 1} (t) i g h t

,

m a t h r m S_{3} (n) = 2^{n} - - 1

. In this paper, we generalize this recurrence relation to

m a t h r m G_{k} (n) = m i n_{1 l e q s l a n t t l e q s l a n t n} l e f t p_{k} c d o t m a t h r m G_{k} (n - t) + q_{k} c d o t m a t h r m G_{k - 1} (t) i g h t

,

m a t h r m G_{3} (n) = p_{3} c d o t m a t h r m G_{3} (n - 1) + q_{3}

, for two sequences of arbitrary positive integers

l e f t (p_{i} i g h t)_{i g e q s l a n t 3}

and

l e f t (q_{i} i g h t)_{i g e q s l a n t 3}

and we show that the sequence of differences

l e f t (m a t h r m G_{k} (n) - m a t h r m G_{k} (n - 1) i g h t)_{n g e q s l a n t 1}

consists of numbers of the form

l e f t (p r o d_{i = 3}^{k} q_{i} i g h t) c d o t l e f t (p r o d_{i = 3}^{k} {p_{i}}^{a l p h a_{i}} i g h t)

, with

a l p h a_{i} g e q s l a n t 0

for all

i

, arranged in nondecreasing order. We also apply this result to analyze recurrence relations for the Tower of Hanoi problems on several graphs.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: On generalized Frame-Stewart numbers