¿Cómo podemos crear arbitrariamente largas instancias del algoritmo de Euclides?

Question

¿Cómo podemos crear arbitrariamente largas instancias del algoritmo de Euclides? ¿Qué tipo de números son útiles? ¿Cuál es la relación entre el tamaño de estos números y el número de pasos?

Answer 1

Para los números de Fibonacci $F_n$, tenemos $$\gcd(F_n, F_{n+1}) = 1,$$ and the number of steps in the Euclidean algorithm is $n$ (if you count the last step as $1 = 1+0$).

Answer 2

Heropup la solución que da a los más pequeños valores para una determinada longitud de la secuencia.

Otro método para obtener una longitud dada del algoritmo de Euclides con una prescrito mcd $=d$ establecer $r_0=0$ $r_1=d$ ($r$ valores serán los restos). A continuación, elija una secuencia de (entero positivo) los cocientes de la longitud deseada, decir $q_1,\dots q_k$. A continuación, establezca $r_{i+1}=q_i\cdot r_i+r_{i-1}$. Esto le dará un Algoritmo de Euclides con $k-1$ (distinto de cero) restos.

Por ejemplo, supongamos que utilizamos $d=3$, y la secuencia de los cocientes $\{2,1,4,1,1\}$. Esto le da a la secuencia de los restos de $0, 3, 6, 9, 42, 51, 93$. Así que nos tomamos nuestro mcd problema a $\gcd(93, 51)$, que nos da un algoritmo de Euclides secuencia con $4$ (distinto de cero) restos.