The subtractive Euclidean algorithm and Fibonacci numbers
Let \(m,n\) be positive integers with \(m>n\). Replacement of \((m,n)\) by \((m-n,n)\) or \((n,m-n)\) leads after \(K\) steps to \((1,0)\). Each pair is given by premultiplication of its successor by one of the matrices \(A\binom {1\;1}{0\;1}\) or \(B\binom {1\;1}{1\;0}\). Powers of \(B\) have Fibonacci numbers as elements. By considering the possible sequences of \(A\)'s and \(B\)'s, the author obtains the known result on the number of pairs of length \(K\), and also obtains the average size of \(m\) for given \(K\). To find the average size of \(K\) for given \(m\) is much harder, as was shown by \textit{D. E. Knuth} and \textit{A. C. Yao} [Proc. Natl. Acad. Sci. USA 72, 4720-4722 (1975; Zbl 0315.10005)].
This page was built for publication: The subtractive Euclidean algorithm and Fibonacci numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746559)
