Find an upper bound for the number of iterations over the Euclidean algorithm

Question

Let $1\leq y\leq x\leq 2020$ be natural numbers.

Find an upper bound for the number of iterations over the Euclidean algorithm on $(x,y)$.

I don't have any idea how to solve it. Is it possible to explain how to find the upper bound? I can run a Python code but I would like to understand the math.

EDIT: Actually tried to run the code but it didn't give me much information.

Answer 1

The highest number of iterations alway occurs when $x(x,y)$ are consecutive Fibonacci numbers so the max number of iterations is the "ordinal" number of the lesser Fibonacci number that is greater than or equal to the lesser of the two inputs. Note that entering the greater number 2nd will result in one more iteration.

Here is a sample run comparing iterations for all pairs up to $100$ and displaying only the first time an iteration count is greater than the previous highest count.

 enter limit? 5000
 iterations( 1 )    GCD( 2 , 1 ) = 1 
 iterations( 2 )    GCD( 3 , 2 ) = 1 
 iterations( 3 )    GCD( 5 , 3 ) = 1 
 iterations( 4 )    GCD( 8 , 5 ) = 1 
 iterations( 5 )    GCD( 13 , 8 ) = 1 
 iterations( 6 )    GCD( 21 , 13 ) = 1 
 iterations( 7 )    GCD( 34 , 21 ) = 1 
 iterations( 8 )    GCD( 55 , 34 ) = 1 
 iterations( 9 )    GCD( 89 , 55 ) = 1 
 iterations( 10 )   GCD( 144 , 89 ) = 1 
 iterations( 11 )   GCD( 233 , 144 ) = 1 
 iterations( 12 )   GCD( 377 , 233 ) = 1 
 iterations( 13 )   GCD( 610 , 377 ) = 1 
 iterations( 14 )   GCD( 987 , 610 ) = 1 
 iterations( 15 )   GCD( 1597 , 987 ) = 1 
 iterations( 16 )   GCD( 2584 , 1597 ) = 1 
 iterations( 17 )   GCD( 4181 , 2584 ) = 1