calcular de manera eficiente todas las ternas pitagóricas conociendo la hipotenusa

Question

Dada una hipotenusa (c en la ecuación típica a*a + b*b = c*c), lo que es una forma eficiente para calcular todos los posibles valores enteros de a y b, de tal manera que a < b?

Nota: He visto c ser mayor que 1e12, por lo tanto c*c es mayor que long.MaxValue, de lo que puedo decir, se adaptan a ninguno c*c un decimal, sin embargo.

Answer 1

Hay una solución matemática que encuentra ayb incluso para valores grandes de c. Desafortunadamente, no es tan simple. Estoy tratando de dar una breve explicación del algoritmo. Espero que no sea demasiado confuso.

Dado que se da c y que busca para a y b, que básicamente quiere resolver diophantine ecuaciones de la forma

n=x^2+y^2, 

donde se da n. No ayuda mucho que n = c * c sea un cuadrado y, por lo tanto, estoy describiendo una solución para cualquier n. Si n fuera un número primo, entonces podría usar Fermat's theorem, para decidir si su ecuación es solvente y usarla, ya que Moron señaló el algoritmo Hermite-Serret para encontrar las soluciones, si las hubiera. Para resolver el caso donde n no es primo, es una buena idea usar Gaussian integers. (Los enteros gaussianos son solo números complejos con coeficientes integrales). En particular, se observa que la norma de x + yi es

N(x+yi) = x^2+y^2. 

Por lo tanto uno tiene que encontrar los enteros de Gauss x + yi cuya norma es n. Dado que la norma es multiplicativa, es suficiente resolver esta ecuación para los factores de ny luego multiplicar los enteros gaussianos de las ecuaciones indivi-duales. Déjeme dar un ejemplo. Queremos resolver

65 = x^2 + y^2. 

Esto es equivalente a encontrar x, y de tal manera que

N(x+yi) = 65 

lo largo de los enteros de Gauss. Factorizamos 65 = 5 * 13, luego usamos Fermat para notar que ambos 5 y 13 se pueden representar como suma de dos cuadrados. Por último, nos encontramos ya sea mediante el uso de la fuerza bruta de mediante el algoritmo de Hermite-Serret

N(2+i) = N(1+2i) = ... = 5 
N(2+3i) = N(3+2i) = ... = 13 

Nota, He dejado de lado los números enteros Gaussion 2-i, -2 + i, etc con coeficientes negativos. Esas son, por supuesto, soluciones también.

Por lo tanto ahora podemos multiplicar estas soluciones en conjunto para obtener

65 = 5 * 13 = N (2 + i) * N (2 + 3i) = N ((2 + i) * (2 + 3i)) = N (1 + 8i)

y

65 = 5 * 13 = N (2 + i) * N (3 + 2i) = N ((2 + i) * (3 + 2i)) = N (4 + 7i).

Por lo tanto, se obtiene las dos soluciones

1*1 + 8*8 = 65 
4*4 + 7*7 = 65 

las otras combinaciones, por ejemplo, con coeficientes negativos deben ser revisados ​​también. No dan nuevas soluciones que no sean permutaciones y signos modificados.

---

Para calcular todas las soluciones también se podría agregar que no es necesario calcular c * c. Encontrar los factores de c es todo lo que es necesario. Además, como a y b son ambos menores que c, no sucederá que los productos de números enteros gaussianos no sean representables con coeficientes enteros de 64 bits. Por lo tanto, si uno es cuidadoso, el entero de 64 bits es suficiente precisión para resolver el problema. Por supuesto, siempre es más fácil usar un lenguaje como Python que no tiene este tipo de problemas de desbordamiento.

Answer 2

También podría ir a una biblioteca de BigNum.

En cuanto a una forma eficaz de encontrar a y b:

Para cada valor de b (a partir de c-1 y bajando hasta b * b < c * c/2), calcular c * c - b * b, y luego verifica si es un cuadrado perfecto.

Answer 3

Comience con un valor de 1 para a y un valor de c para b.

Comparar c*c - b*b a a*a. Si son iguales, tienes una coincidencia.

Cambie ayb entre sí dependiendo de qué lado sea más grande, hasta que sean iguales.

Answer 4

Dado un c:

Desde b> a, si a es mínimo (a = 1), b = sqrt (c * c - 1).

Por lo tanto, b DEBE estar entre ese valor y c -1.

Además, como b debe ser un número entero, debe encontrar el primer valor para el que este es un número entero.

Now, a property of squares: 
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ... 
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ... 
That means a square can be written as a summation of ODD numbers: 
    1 + 3 + 5 + 7 + n+... 
where n = number the summation is a square of. 

Así que hay exactamente c números cuadrados menores que c * c, y puede identificarlos usando la sustracción simple.

Volviendo al principio, tomando b = sqrt (c c - 1), redondeando hacia abajo y tomando b b, obtenemos la plaza b debe estar por encima, y ​​una a = 1. Encontrar c c - (a a + b b). Esto debería darle el número que se debe AGREGAR para lograr c * c.

Ya que se puede añadir a un 3 + 5 + 7 + ... y b+2 + b+4 + b+6 + ... ab, sólo hay que encontrar el término adecuado en función de las sumas en lugar de la plaza en sí :)

Answer 5

Todas las ternas pitagóricas (a, b, c) satisfacer la propiedad de que, para algunos números enteros k, m y n,

a = k (m^2-n^2), b = 2kmn, c = k (m^2 + n^2)

Así que comience por factorizar c. Luego, para cada factor distinto k de c (es decir, para cada subconjunto distinto de los factores, multiplicados juntos), encuentre todos los m y n que satisfacen c/k = (m^2 + n^2). Hacer esto último requerirá mucho menos tiempo que el enfoque de fuerza bruta que otros han sugerido (solo tienes que encontrar cuadrados que sumen c/k, en lugar de c^2), pero identificará todos los triples (a, b, c) . Tampoco es necesario utilizar bignums, porque todos los resultados intermedios se ajustan a una larga.

También sugiero que revise la página web http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html bajo el título "Una calculadora triple pitagórica más general" que contiene una calculadora incrustada, escrita en javascript, que hace exactamente lo que desea.