Izvorni znanstveni članak
Ties in Worst-Case Analysis of the Euclidean Algorithm
Brian Hopkins
; Saint Peter’s University, Jersey City, NJ 07 306 USA
Aram Tangboonduangjit
; Mahidol University International College, 999 Phutthamonthon Sai 4 Rd, Salaya, Phutthamonthon District, Nakhon Pathom 73 170, Thailand
Sažetak
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.
Ključne riječi
Euclidean algorithm; continuant polynomials; Fibonacci numbers
Hrčak ID:
252595
URI
Datum izdavanja:
10.3.2021.
Posjeta: 1.107 *