Aritmética¶

En esta sesión vamos a trabajar con algunas funciones de Sage para trabajar con números (algunas ya las hemos usado), y a implementar algunos algoritmos clásicos de teoría de números.

Esta vez no vamos a separar la teoría de los ejercicios . En realidad, no vamos a usar funciones de Sage ni características de Sage que no hayamos visto antes. Debajo tienes varios temas de teoría de números, con una pequeña introducción y un recordatorio de algunas funciones que pueden ser útiles, y de varios ejercicios de dos grupos. El primer grupo consiste de ejercicios básicos que deberías intentar resolver en esta misma sesión. El segundo grupo consiste de ejercicios para resolver en casa . La siguiente sesión resolveremos buena parte de los ejercicios.

Dígitos de un número en una base arbitraria¶

Aunque hemos escrito nuestra propia función para recuperar los dígitos de un número en una base B arbitraria (o casi), también podemos usar el método digits , que tienen los enteros de Sage ( Integer ).

sage: a = 17
sage: print a.digits(base=2)
sage: print a.digits(base=10)
sage: print a.digits(base=3)
[1, 0, 0, 0, 1]
[7, 1]
[2, 2, 1]

Sin embargo, no he podido encontrar la función inversa.

Ejercicio¶

Escribe una función que acepta como argumentos:

una lista de enteros (los dígitos)

un entero (la base)

y devuelve el entero que tiene esa lista de dígitos en esa base.

Ejercicios para casa¶

1.¶

Escribe una función que devuelva True si un número es divisible por 9 usando el criterio que dice: “un número es divisible por 9 si y sólo si la suma de sus dígitos es divisible por 9”. Si la suma de los dígitos es mayor que 9, puedes llamar a la función recursivamente para decidir si verifica el criterio. No debería usar el resto de la división ( % ) en ningún momento.

2.¶

El método reverse invierte los elementos de una lista.

lista = [2,4,7]
lista.reverse()
print lista

> [7,4,2]

Utiliza este método y las técnicas de este capítulo para construir:

Una función que acepta un número y te devuelve otro número, con las mismas cifras que el anterior pero en orden inverso.

Una función que acepta un número y devuelve un booleano: True si es palíndromo (se lee igual de derecha a izquierda que de derecha a izquierda) y False si no lo es.

3.¶

http://projecteuler.net/index.php?section=problems&id=36

Encuentra todos los números menores que un millón que son palíndromos tanto en base 2 como en base 10 .

Por ejemplo, 585 se escribe 1001001001 en binario. Ambas expresiones se leen igual al derecho que al revés.

Números primos¶

is_prime(k) : Comprueba si k es primo.

next_prime(k) : Devuelve el menor número primo mayor que k.

prime_range(k) : Lista de primos menores que k.

factor(k): factorización de k. list( factor(k) ) devuelve una lista de tuplas con cada factor y su exponente correspondiente.

Ejercicios¶

Infinitos primos en cualquier combinación lineal¶

El teorema de Dirichlet dice que hay infinitos números primos en una sucesión del tipo:

$x_j=a\cdot j+b$

siempre que a y b sean números primos entre sí.

http://es.wikipedia.org/wiki/Teorema_de_Dirichlet

Dados tres números a, b y N, encuentra el menor número primo de la forma aj+b con j mayor que N:

Teorema del número primo¶

El teorema del número primo afirma que el siguiente límite existe y es igual a 1:

$\lim_{x\to\infty}\frac{\pi(x)}{x/\ln(x)}$

donde $\pi(x)$ es la cantidad de números primos menores que x y ln(x) es el logaritmo neperiano.

Escribe un código que evalúe la función $\frac{\pi(x)}{x\: ln(x)}$ para un número x cualquiera.

Encuentra un número x tal que el límite diste de 1 menos de 0.1

Ejercicios para casa¶

1.¶

Halla la secuencia más larga de números consecutivos menores que un millón que no contiene ningún primo.

2.¶

La función $\phi$ de Euler se puede calcular utilizando la factorización del número. Si $k=p_1^{e_1}\dots p_k^{e_k}$ , tenemos:

$\phi(k)=\prod (p_j^{e_j}-p_j^{e_{j}-1})$

Utiliza el método factor aplicado a números enteros y la fórmula de arriba para calcular el valor de la función $\phi$ de Euler:

Compara el resultado con el obtenido usando la regla “ $\phi(k)$ es la cantidad de números menores que k que son primos relativos con k”, o bien con alguna función de Sage que haga la misma tarea.

Algoritmo de Euclides¶

El algoritmo de euclides calcula el máximo común divisor ( mcd ) de dos números naturales n y m. El algoritmo se basa en el siguiente principio: el mcd de dos números n y m, con n<m, es también el mcd de n y m%n (el resto de dividir m por n). De esta forma, hemos reducido el problema a otro con números menores. Eventualmente, uno de los dos números será 0, y entonces sabemos que mcd(0,m)=m.

Ejercicios¶

1.¶

Escribe una función que calcule el máximo común divisor de dos números siguiendo el algoritmo de Euclides.

2.¶

Escribe una función que acepte una lista de números como argumento y devuelva el máximo común divisor de los números de la lista.

Ejercicio para casa¶

Escribe una función que calcule el máximo común divisor de dos números calculando la factorización de cada uno de ellos y después escogiendo los factores comunes con el menor exponente.

Identidad de Bezout¶

Una identidad de Bézout muestra explícitamente el mcd d de m y n como una combinación lineal de m y n con coeficientes enteros:

$d=u\: m+v\: n$

La función xgcd de SAGE implementa el algoritmo extendido de Euclides, que devuelve una tupla con el mcd y los coeficientes de una identidad de Bézout:

(d,u,v)=xgcd(m,n)

sage: m=15
sage: n=21
sage: (d,u,v)=xgcd(m,n)
sage: print '%d=(%d)*%d+(%d)*%d'%(d,u,m,v,n)
3=(3)*15+(-2)*21

Identidad de Bézout con más de dos números.¶

También podemos encontrar una identidad del tipo

$d=\sum_{j=1}^N u_j m_j$

donde d es el máximo divisor común a todos los números $m_j$ . De hecho, el proceso para encontrarlo se reduce al anterior, usando inducción. Como ya sabemos resolver el caso N=2 , sólo tenemos que aprender a reducir el caso de N+1 números al caso anterior.

Para unos números $m=m_1,\dots, m_{N+1}$ , comenzamos por encontrar una identidad de Bezout para los dos últimos:

$d_N=v\:m_N+w\:m_{N+1}$

Después aplicamos la hipótesis de inducción a $m_1,\dots,m_{N-1},d_N$ :

$d=\sum_{j=1}^{N-1} u_j m_j+u_N d_N$

El mcd de $m_1,\dots,m_{N-1},d_N$ es también el de $m_1,\dots,m_{N+1}$ , así que sólo tenemos que sustituir:

$d=\sum_{j=1}^{N-1} u_j m_j+u_N (v\:m_N+w\:m_{N+1})$

Ejercicio¶

Escribe una función que acepta como argumento una lista de números $m_j$ y devuelve una lista que contiene en primer lugar el máximo común divisor de todos los elementos de la lista, seguido de los ceficientes $u_j$ que realizan la identidad:

$d=\sum_{j=1}^N u_j m_j$

Teorema chino del resto¶

Con la identidad de Bézout podemos hacer funcionar el teorema chino del resto:

Si los números m y n son primos entre sí, entonces para cualesquiera a<m , b<n existe un único número c menor que n*m tal que el resto de dividir c entre m es a y el resto de dividir c entre n es b .

En lenguaje de congruencias, escribimos $x\equiv a (mod\; m)$ para decir que el resto de dividir a por m es el mismo que el resto de dividir x por m . El teorema chino del resto se escribe entonces:

$x\equiv a (mod\; m), x\equiv b (mod\; n)\iff x\equiv c (mod\; nm)$

Se puede comprobar que podemos obtener c de la fórmula:

$c=bmv+anu$

donde $u$ y $v$ vienen de una identidad de Bézout:

$1=nu + mv$

Ejercicio¶

Escribe una función que, dados a, m, b y n, devuelva c.

Generaliza el resultado a varias congruencias $x\equiv a_i (mod\; m_i)$ , para $i=1\dots N$ , donde todos los números $m_i$ son primos entre sí, y escribe una función que acepte una lista con los números $m_i$ y otra con los números $a_i$ y devuelva un número $c$ tal que:

$x\equiv a_i (mod\; m_i) \forall i \iff x\equiv c (mod\; m_1\cdot\dots\cdot m_N)$

Aritmética¶

Dígitos de un número en una base arbitraria¶

Ejercicio¶

Ejercicios para casa¶

1.¶

2.¶

3.¶

Números primos¶

Ejercicios¶

Infinitos primos en cualquier combinación lineal¶

Teorema del número primo¶

Ejercicios para casa¶

1.¶

2.¶

Algoritmo de Euclides¶

Ejercicios¶

1.¶

2.¶

Ejercicio para casa¶

Identidad de Bezout¶

Identidad de Bézout con más de dos números.¶

Ejercicio¶

Teorema chino del resto¶

Ejercicio¶

Contenidos

Tema anterior

Próximo tema

Esta página

Navegación

Aritmética¶

Dígitos de un número en una base arbitraria¶

Ejercicio¶

Ejercicios para casa¶

1.¶

2.¶

3.¶

Números primos¶

Ejercicios¶

Infinitos primos en cualquier combinación lineal¶

Teorema del número primo¶

Ejercicios para casa¶

1.¶

2.¶

Algoritmo de Euclides¶

Ejercicios¶

1.¶

2.¶

Ejercicio para casa¶

Identidad de Bezout¶

Identidad de Bézout con más de dos números.¶

Ejercicio¶

Teorema chino del resto¶

Ejercicio¶

Contenidos

Tema anterior

Próximo tema

Esta página

Búsqueda rápida

Navegación