Ties in Worst-Case Analysis of the Euclidean Algorithm

Authors :: Brian Hopkins
Aram Tangboonduangjit
Brian Hopkins
Aram Tangboonduangjit
Source :: Mathematical Communications; ISSN 1331-0623 (Print); ISSN 1848-8013 (Online); Volume 26; Issue 1
Publication Year :: 2021
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.

Database :: OAIster
Journal :: Mathematical Communications; ISSN 1331-0623 (Print); ISSN 1848-8013 (Online); Volume 26; Issue 1
Notes :: application/pdf, English
Publication Type :: Electronic Resource
Accession number :: edsoai.on1363264750
Document Type :: Electronic Resource