Ties in Worst-Case Analysis of the Euclidean Algorithm

Brian Hopkins; Aram Tangboonduangjit

Vol. 26 No. 1 (2021)

Regular Articles

Ties in Worst-Case Analysis of the Euclidean Algorithm

Published 2021-02-23

Brian Hopkins
Aram Tangboonduangjit

Submission of an original manuscript to the Mathematical Communications will be taken to mean that it represents original work not previously published, that it is not being considered elsewhere for publication; and, if accepted for publication, it will be published in print and online form and it will not be published elsewhere in the same form, for commercial purposes, in any language, without the consent of the publisher. The journal takes the stance that the publication of scholarly research is meant to disseminate knowledge and, in a not-for-profit regime, benefits neither publisher nor author financially. It sees itself as having an obligation to its authors and to society to make content available online now that the technology allows for such a possibility.

Abstract

We determine all pairs of positive integers below a given bound that require the most division steps in the Euclidean algorithm. Also, we find asymptotic probabilities for a unique maximal pair or an even number of them. Our primary tools are continuant polynomials and the Zeckendorf representation using Fibonacci numbers.

Keywords

Euclidean algorithm, continuant polynomials, Fibonacci numbers

PDF

Supplementary File(s)

Tex

Author Biography

Brian Hopkins

Department of Mathematics, professor