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

  • x,y,z sean menores o iguales a N
  • x,y,z sean primos relativos (es decir que 1 es su único divisor común)
  • x < y < z

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:

comparacion

mmm, hay que pensar una mejor solución.

         
0 votos

5 Responses to “Fermat vs. Pythagoras”

  1. Vientos de Libertad » Blog Archive » Fermat vs. Pythagoras mejorado says:

    […] El contenido de este sitio web es licenciado bajo Creative Commons License. Excepto que se explicite lo contrario. « Fermat vs. Pythagoras […]

  2. RAUL SIERRA says:

    HAY UNA TOTAL ARMONIA ENTRE EL TEOREMA DE PITAGORAS Y EL ULTIMO TEOREMA DE FERMAT.
    EN www.raul-sierra.com.ve LO EXPLICO DE FORMA SENCILLA Y CLARA, CON PRUEBA FISICA, INTERPRETACION GRAFICA Y FORMULAS PARA ENCONTRAR INFINITAS SOLUCIONES EN AMBOS TEOREMAS.

  3. Antonino says:

    Hola Juan Pablo, me tope con tu página de casualidad mientras buscaba una pagina de la facu, yo también estudio en la UTN-FRSF y me interesó tu problema de programación relacionado al teorema de Fermat.
    Tengo una duda, que lográs encontrar mediantes los calculos relacionados con el teorema de Fermat??

    Cual es el objetivo de los cálculos.

    Sigo viendo tu página.

    Saludos!

    AUS Antonino Ferrando

  4. Juanjo says:

    Hola Antonino! Este.. soy Juanjo (por Juan José) :-)

    Vos te referís a cuando lo usa alguien haciendo matemáticas? Viste como son los matemáticos, algo no tiene que tener un fin en concreto para existir en su mundo ;-)

    Sobre el Teorema de Fermat:

    Si n es un número entero mayor que 2 (o sea, n > 2), entonces no existen números enteros x, y y z (excepto las soluciones triviales, como x = 0 ó y = 0 ó z = 0) tales que cumplan la igualdad:

    z^n = x^n + y^n (nota, ^ representa la potencia)

    Pierre de Fermat escribió en el margen de su copia del libro Aritmética de Diofanto, traducido por Claude Gaspar Bachet, en el problema que trata sobre la división de un cuadrado como suma de dos cuadrados (z2 = x2 + y2):

    Es imposible dividir un cubo en suma de dos cubos, o un bicuadrado en suma de dos bicuadrados, o en general, cualquier potencia superior a dos en dos potencias del mismo grado; he descubierto una demostración maravillosa de esta afirmación. Pero este margen es demasiado angosto para contenerla.

    Por otro lado MI objetivo al resolver el problema del enunciado (que si te fijás tiene más que ver con Pitágoras que con Fermat) fué ejercitar mis habilidades en el lenguaje de programación Python.

  5. giovanni says:

    pues creo que lo que quiere decir es que pitagoras se aplica en todas las dimenciones no?

Dejar una respuesta

Line and paragraph breaks automatic.
XHTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>