IEICE TRANSACTIONS on Information
Analysis of Recurrence Relations Generalized from the 4-Peg Tower of Hanoi
Summary :
In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min 1 ≤ t ≤ n {αT(n-t,α,β) + βS(t,3)} , where S(t,3) = 2t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n,α,β)'s, i.e., {T(n,α,β) - T(n-1,α,β)}, consists of numbers of the form β 2i αj (i, j ≥ 0) lined in the increasing order.
- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.220-225
- Publication Date
- 2011/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E94.D.220
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akihiro MATSUURA, "Analysis of Recurrence Relations Generalized from the 4-Peg Tower of Hanoi" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 220-225, February 2011, doi: 10.1587/transinf.E94.D.220.
Abstract: In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min 1 ≤ t ≤ n {αT(n-t,α,β) + βS(t,3)} , where S(t,3) = 2t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n,α,β)'s, i.e., {T(n,α,β) - T(n-1,α,β)}, consists of numbers of the form β 2i αj (i, j ≥ 0) lined in the increasing order.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.220/_p
Copy
@ARTICLE{e94-d_2_220,
author={Akihiro MATSUURA, },
journal={IEICE TRANSACTIONS on Information},
title={Analysis of Recurrence Relations Generalized from the 4-Peg Tower of Hanoi},
year={2011},
volume={E94-D},
number={2},
pages={220-225},
abstract={In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min 1 ≤ t ≤ n {αT(n-t,α,β) + βS(t,3)} , where S(t,3) = 2t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n,α,β)'s, i.e., {T(n,α,β) - T(n-1,α,β)}, consists of numbers of the form β 2i αj (i, j ≥ 0) lined in the increasing order.},
keywords={},
doi={10.1587/transinf.E94.D.220},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Analysis of Recurrence Relations Generalized from the 4-Peg Tower of Hanoi
T2 - IEICE TRANSACTIONS on Information
SP - 220
EP - 225
AU - Akihiro MATSUURA
PY - 2011
DO - 10.1587/transinf.E94.D.220
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2011
AB - In this paper, we analyze recurrence relations generalized from the Tower of Hanoi problem of the form T(n,α,β) = min 1 ≤ t ≤ n {αT(n-t,α,β) + βS(t,3)} , where S(t,3) = 2t - 1 is the optimal total number of moves for the 3-peg Tower of Hanoi problem. It is shown that when α and β are natural numbers, the sequence of differences of T(n,α,β)'s, i.e., {T(n,α,β) - T(n-1,α,β)}, consists of numbers of the form β 2i αj (i, j ≥ 0) lined in the increasing order.
ER -
English
