Python para Bioinformática: triples pitagóricos

Una terna pitagórica es un conjunto de números enteros a, b y c tales que

a ^ 2 + b ^ 2 = c ^ 2

Queremos triples primitivos, aquellos en los que a, b y c no tienen factor común.

Euclides presenta un fórmula para eso: tome dos enteros cualesquiera n > m > 0, entonces

b = 2 minutos
a = n^2 – m^2
c = n ^ 2 + m ^ 2

Una restricción más: m y n no deben tener ningún factor común, deben ser coprimos, de lo contrario el triple no será primitivo.

Es fácil demostrar que cuando a, b y c se encuentran de esta manera, satisfacen la ecuación de Pitágoras.

El truco es ver de dónde viene esto y, lo que es más importante, demostrar que describe todo tales triples.

Derivación

Encontré una muy buena derivación en maor (El teorema de Pitágoras). Comenzamos investigando las propiedades de a, b y c.

Por ejemplo, a y b no pueden ser pares, porque en ese caso, c también será par, y entonces hay un factor común.

Recuerde que cualquier número par se puede escribir como 2k, y cualquier número impar como 2k + 1 para el entero positivo k (o k = 0 para n = 1), por lo que es fácil ver que si n es par, también lo es n^ 2. Y si n es impar entonces también lo es n^2. Por lo tanto, un cuadrado par perfecto implica una raíz cuadrada entera par, y un cuadrado impar implica una raíz impar.

En el caso de que a y b sean ambos impares, c debe ser par, ya que impar más impar es igual a par. Para ver un problema con esto, reescriba la ecuación

(2i + 1)^2 + (2j + 1)^2 = (2k)^2

El lado izquierdo no es múltiplo de 4, pero el lado derecho sí lo es. Esto es imposible. Por tanto, uno de a o b debe ser par y el otro impar. Sea a extraño. Entonces b se puede escribir como b = 2t para algún entero t. Tenemos

(2t)^2 = c^2 – a^2 = (c + a)(c – a)

Cada a, b y c deben satisfacer esta ecuación. Además, vemos que hay un factor de 4 en el lado izquierdo, por lo que podemos obtener un divisor de 2 para cada factor de la derecha:

t^2 = (c + a)/2 . (c-a)/2

a y c son ambos impares:

a = 2i + 1
c = 2k + 1

por lo que su suma y diferencia son pares, ya que

2k + 1 + 2i + 1 = 2(k + i) + 2
2k + 1 – 2i – 1 = 2(k – yo)

Después de cancelar el factor de 2 obtenemos

(c + a)/2 = k + yo + 1
(c – a)/2 = k – yo

Por lo tanto, ambos factores del lado derecho son números enteros, mientras que el lado izquierdo (t ^ 2) es un cuadrado perfecto.

Paso clave

Aquí está el último paso. Afirmamos que estos dos términos no tienen un factor común.

Siempre que x e y tienen un factor común, también lo tienen su suma y diferencia ya que x + y = fp + fq = f(p + q). etcétera. Lo contrario también es cierto.

Pero la suma y la diferencia de estos términos son:

(c + a)/2 + (c – a)/2 = c
(c + a)/2 – (c – a)/2 = a

En la suposición de que (c+a)/2 y (ca)/2 tenían un factor común, entonces compartirían ese factor común con ambos c y a. Como sabemos que a y c (al menos los que nos interesan en particular) no tienen un factor común, tampoco lo tienen estos dos términos.

Entonces, los dos términos no tienen factor común y, sin embargo, se multiplican para dar un cuadrado perfecto.

t no puede ser primo en sí mismo (porque no habría dos factores diferentes).

Entonces, claramente hay dos factores m ^ 2 y n ^ 2 (m y n no necesariamente primos), ¡y ambos términos son cuadrados perfectos! Escribir:

n^2 = (c + a)/2
m^2 = (c – a)/2

n^2 + m^2 = c
n^2 – m^2 = un

Y

m^2n^2 = t^2
mn = t

Desde b^2 = 4t^2, b = 2t = 2mn.

Estas propiedades de m y n se derivan de las reglas estándar sobre factores, aplicadas a a, b y c. Por lo tanto, cualquier triple a, b y c se puede escribir en términos de un número entero m y n mediante este método.

Verifiqué esto usando un script de Python para buscar en todo el espacio de cuadrados por debajo de un límite arbitrario, para aquellos que suman para dar otro cuadrado, manteniendo solo esos triples de cuadrados sin factores comunes.

Probé cada triple tomando el miembro par, dividiéndolo por 2 y luego encontrando sus factores. Esto da pares de candidatos m y n con 2mn = segundo. Luego, solo verifique si n^2 – m^2 = un.

la esencia es aquí.

Es interesante ver qué patrones entre los triples provienen de qué elecciones de m y n.