×

The Towers of Hanoi and binary numerals. (English) Zbl 0578.68054

An interesting relation between the Towers of Hanoi and the binary numerals is proved; that is, the disc to be moved in step x is precisely the position of the rightmost 1 in the binary representation of x, if the discs are numbered 1,2,3,...,n from the smallest to the largest. A simple iterative algorithm for solving the Towers of Hanoi problem is also presented, using the above relation. Finally, an observation concerning the iterative programming is made.

MSC:

68R99 Discrete mathematics in relation to computer science
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ball R. R. W., Mathematical recreations and essays (1982)
[2] Barnard D. T., Technical Report 80–103, in: The Towers of Hanoi: An exercise in non-recursive algorithm development (1980)
[3] Buneman P., Information Processing Letters 10 pp 243– (1980) · Zbl 0439.05010 · doi:10.1016/0020-0190(80)90150-7
[4] Dijkstra E. W., A short introduction to the art of programming (1971)
[5] Er M. C., The Computer Journal 25 pp 442– (1982) · Zbl 0493.90100 · doi:10.1093/comjnl/25.4.442
[6] Hayes P. J., The Computer Journal 20 pp 282– (1977) · Zbl 0362.68057 · doi:10.1093/comjnl/20.3.282
[7] Minsker S., Three variations on the Towers of Hanoi problem (1983)
[8] Walsh T. R., Information Processing Letters 15 pp 64– (1982) · Zbl 0487.90099 · doi:10.1016/0020-0190(82)90108-9
[9] Wood D., J. Recreational Mathematics 14 pp 17– (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.