Ties in worst-case analysis of the euclidean algorithm

Brian Hopkins; Aram Tangboonduangjit

Ties in worst-case analysis of the euclidean algorithm

Brian Hopkins
, Aram Tangboonduangjit

Science Division

Saint Peter’s University

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

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

Original language	English
Pages (from-to)	9-20
Number of pages	12
Journal	Mathematical Communications
Volume	26
Issue number	1
Publication status	Published - 2021

Keywords

Continuant polynomials
Euclidean algorithm
Fibonacci numbers

Cite this

@article{1a612bc7717c4be79ba24dd1a754fc0f,

title = "Ties in worst-case analysis of the euclidean algorithm",

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

keywords = "Continuant polynomials, Euclidean algorithm, Fibonacci numbers",

author = "Brian Hopkins and Aram Tangboonduangjit",

note = "Publisher Copyright: {\textcopyright} 2021 Department of Mathematics, University of Osijek.",

year = "2021",

language = "English",

volume = "26",

pages = "9--20",

journal = "Mathematical Communications",

issn = "1331-0623",

publisher = "Udruga Matematicara Osijek",

number = "1",

}

TY - JOUR

T1 - Ties in worst-case analysis of the euclidean algorithm

AU - Hopkins, Brian

AU - Tangboonduangjit, Aram

PY - 2021

Y1 - 2021

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

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

KW - Continuant polynomials

KW - Euclidean algorithm

KW - Fibonacci numbers

UR - https://www.scopus.com/pages/publications/85103018881

M3 - Article

AN - SCOPUS:85103018881

SN - 1331-0623

VL - 26

SP - 9

EP - 20

JO - Mathematical Communications

JF - Mathematical Communications

IS - 1

ER -

Ties in worst-case analysis of the euclidean algorithm

Abstract

Keywords

Other files and links

Fingerprint

Cite this