.. -*- coding: utf-8 -*- 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. .. index:: digits 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. .. index:: is_prime, next_prime, prime_range, factor 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: .. MATH:: 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: .. MATH:: \lim_{x\to\infty}\frac{\pi(x)}{x/\ln(x)} donde :math:`\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 :math:`\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 :math:`\phi` de Euler se puede calcular utilizando la factorización del número. Si :math:`k=p_1^{e_1}\dots p_k^{e_k}`, tenemos: .. MATH:: \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 :math:`\phi` de Euler: - Compara el resultado con el obtenido usando la regla ":math:`\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