Fermat vs. Pythagoras

Esta es mi solución al problema número 6 de una larga lista de problemas de programación. A pesar de que, como estudiante de Ingeniería, pasé los últimos 3 años y medio estudiando distintas formas de las matemáticas, no conocí el Último Teorema de Fermat hasta que mi amigo Joel, estudiante de Filosofía, me lo comentó.

El problema en realidad no tiene mucho que ver con Fermat, pero sí con Pitágoras: dado un valor N, hay que encontrar cuántos tripletes x,y,z satisfacen x² + y² = z² tales que

<li>x,y,z sean menores o iguales a N</li>

<li>x,y,z sean primos relativos (es decir que 1 es su único divisor común)</li>

<li>x &lt; y &lt; z</li>

Además hay que encontrar cuántos números mayores que 0 y menores o iguales a N no pertenecen a ninguno de los tripletes (no solo a los tripletes de primos relativos).

El enunciado original aquí.

Una posibilidad sería explorar exasutivamente todas las combinaciones de números x,y,z menores o iguales a N, y para cada uno verificar si cumplen las características pedidas. Pero esto sería de altísima complejidad, sería de orden cúbico. Hay que pensar una mejor solución.

Empecemos con una función que dado 3 valores x,y,z me diga si satisfacen el Teorema de Pitágoras:

from math import pow



def pythagoras(x,y,z):

    return (pow(x,2)+pow(y,2) == pow(z,2))

>>> pythagoras(3,4,5)

True

>>> pythagoras(1,1,1)

False

>>> pythagoras()

True

También necesito una función, que dado 3 valores x,y,z me diga sin son primos relativos entre sí:

def mcd(a,b): # algoritmo de euclides

    if (a == b): return a

    elif (a < b): a,b = b,a # a es el más grande

    while(b != 0):

        r = a % b

        a = b

        b = r

        return a



def rprim(x,y,z):

    return (mcd(mcd(x,y),z) == 1)

La solución que explora todas las combinaciones de 3 números constaría de 3 ciclos for anidados y en el curerpo del más profundo se haría las preguntas pertitenes a la resolución del problema: ¿ese triplete satisface el teorema de pitagoras? ¿son primos relativos? ¿x<y<z?

for(x=1;x=<N;x++)

    for(y=1;y=<N;y++)

        for(z=1;z=<N;z++)

            # ¿...?

Una de las condiciones es que x<y<z, esto permite una redefinición tal que NO se exploren todas las combinaciones de 3 números menores que N sino solo las combinaciones que cumplen con esta restricción:

for(x=1;x=<N-2;x++)

    for(y=x+1;y=<N-1;y++)

        for(z=y+1;z=<N;z++)

            # ¿..?

¿Esta solución es buena o no es mucho mejor a una en la que todos los ciclos for vayan de 1 a N y por cada uno se pregunte si x,y,z?

En el archivo pythagoras.py están definidas dos funciones: solv106s(N), basada en la primera aproximación y solv106(N) que espera ser mejor.

Este programita sirve para medir el tiempo de las dos ejecuciones y compararlos.

import timing



def test(N=1000):

    timing.start()

    solv106s(N)

    timing.finish()

    print "la primer solución tardo " + str(timing.seconds()) + " segundos"

    timing.start()

    solv106(N)

    timing.finish()

    print "la segunda solución tardo " + str(timing.seconds()) + " segundos"

Hago una prueba con un valor relativamente grande, N=1000 el valor por defecto:

>>> test()

la primer solución tardo  1879 segundos

la segunda solución tardo 1561 segundos

31 minutos contra 26 minutos.. no me parece una diferencia muy grande. Nota: mi máquina es un AMD K6 II de 700 Mhz.

Esta gráfica compara las dos soluciones luego de haberlas probado con diferentes valores de N, obtenido unos puntos e interpolar una curva representativa:

mmm, hay que pensar una mejor solución.