.. -*- 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<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.


.. index:: xgcd

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:


.. MATH::
    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


.. MATH::
    d=\sum_{j=1}^N u_j m_j


donde d es el máximo divisor común a todos los números :math:`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 :math:`m=m_1,\dots, m_{N+1}`, comenzamos por encontrar una identidad de Bezout para los dos últimos:


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


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


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


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


.. MATH::
    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 :math:`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 :math:`u_j` que realizan la identidad:


.. MATH::
    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 :math:`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:


.. MATH::
    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:


.. MATH::
    c=bmv+anu


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


.. MATH::
    1=nu + mv

Ejercicio
~~~~~~~~~

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


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




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