GIIT_AMA_1718_T1_Tutorial 1

553 days ago by GIIT_AMA_1718

Teoría de números

División de enteros

Sage permite operar con números enteros, algo que no es habitual en los lenguajes de programación (normalmente los ordenadores trabajan con los números enteros entre dos valores):

123^123 
       

Y sobre ellos admite múltitud de operaciones:

# Resto de la división 131432545234324%3243243 
       
%timeit # Factorizar list(factor(34234323294873242342389472324234234324324324321)) 
       

Cuando el número crece, el tiempo de factorización puede aumentar:

%timeit factor(123434234323294873242342389472324234234324324324321) 
       

Factorizar es una operación costosa (incluso con algoritmos optimizados como los que usa Sage). De hecho, se ofrece bastante dinero por factorizar ciertos números.

Sin embargo, podemos calcular el máximo común divisor (utilizardo el algoritmo de euclides) muy rápidamente.

%timeit gcd(123434234323294873242342389472324234234324324324321,34234323294873242342389472324234234324324324321) 
       

Algoritmo de Euclides

Vamos a codificar nosotros mismo el algoritmo, para ver que incluso una versión no optimizada es muy rápida:

%timeit a=123434234323294873242342389472324234234324324324321 b=34234323294873242342389472324234234324324324321 r=a%b while r!=0: a=b b=r r=a%b b 
       

Algoritmo de Euclides extendido

Además de calcular el máximo común divisor, recordemos que el algoritmo de Euclides nos permite calcular los números $x,y$ tales que $mcd(a,b)=ax+by$. Vamos a tratar de programarlo.

# Tomamos dos números como ejemplo a=55324 b=544325 # Guardamos una copia a0=a b0=b 
       
# Calculamos la secuencia de cocientes y restos r=a%b cocientes=[] while r!=0: cocientes=[a//b]+cocientes a=b b=r r=a%b b 
       
# Calculamos x e y a partir de los cocientes: x=1 y=-cocientes[0] for c in cocientes[1:]: x,y=y,x-c*y print x,y 
       

Comprobamos que es correcto.

x*a0+y*b0-b 
       

Criba de Eratóstenes

Un elemento esencial para tratar de factorizar números es la criba de Eratóstenes, que es un método eficiente de obtener la lista de números primos hasta un número dado. La criba se basa en partir de la lista de números e ir eliminando aquellos que sean múltiplos de un número.

n=100 lista=[2..n] for a in [2..n]: for b in [2..n//a]: lista[a*b-2]=0 [p for p in lista if p!=0] 
       
# Gráficamente: n=99 lista=[2..n] p_numeros=sum([text(k,(k//10,k%10),color='black') for k in lista]) p_eliminados=[] for a in [2..n]: alpha=0.5 # Establecemos el umbral mínimo de intensidad para los colores color=(alpha+random()*(1-alpha),alpha+random()*(1-alpha),alpha+random()*(1-alpha)) # Tomamos un color claro al azar for b in [2..n//a]: if lista[a*b-2]!=0: p_eliminados+=[(a*b,color)] lista[a*b-2]=0 sum([point((k//10,k%10),color=color,size=500,axes=false) for k,color in p_eliminados])+p_numeros 
       

Ejercicios

1. Encontrar un número de modo que el Sage tarde en factorizarlo más de 2 segundos (en el desplegable de arriba tiene acción->interrumpir por si el cálculo tarda demasiado).

2. Convertir el algoritmo de Euclides en una función que reciba dos números enteros y devuelva el máximo común divisor.

3. Convertir el algoritmo de Euclides en una función recursiva que reciba dos números enteros y devuelva el máximo común divisor.

4. Calcular los números correspondientes a $ax+by$, con $a=24$, $b=14$ y $x,y$ entre $-10$ y $10$. ¿Cuál podría ser su máximo común divisor a raíz de lo anterior?

5. Crear una función que devuelva los números x,y dados por la Identidad de Bezout.

6. (Para valientes) Crear una versión recursiva de la función anterior.

7. La versión proporcionada de la criba de Eratóstenes no es eficiente. Se pueden realizar las siguientes mejoras:

a) No es necesario eliminar los múltiplos de todos los números hasta $n$, sino hasta $\sqrt(n)$ ¿Por qué?

b) Tampoco hay que eliminar los múltiplos de un número que ya hayamos eliminado.

c) No hace falta comenzar los múltiplos por 2*a. Se puede comenzar por números más grandes. ¿Por cuál?

  Programa la función que genera la criba de Eratóstenes aplicando las mejoras anteriores.

8. (Para valientes) Modifica la función anterior para que también devuelva un esquema de la eliminación de los números (como en el ejemplo). Permite elegir el número de puntos que se representarán en vertical.