efficiente calcolando tutti terne pitagoriche conoscendo il hypoteneuse

Question

Dato un hypoteneuse (c nella tipica equazione a*a + b*b = c*c), ciò che è un modo efficiente per calcolare tutti i possibili valori interi di a e b, tali che a < b?

Nota: Ho visto c essere maggiore di 1e12, quindi c*c è maggiore di long.MaxValue, da quello che posso dire, c*c si adatta in un decimal, però.

Answer 1

C'è una soluzione matematica che trova a e b veloce anche per valori elevati di c. Sfortunatamente, non è così semplice. Sto cercando di dare una breve spiegazione dell'algoritmo. Spero non sia troppo confuso.

Poiché c è dato e siete alla ricerca di A e B, che, fondamentalmente, vuole risolvere Diophantine equazioni della forma

n=x^2+y^2, 

in cui è dato n. Non aiuta molto che n = c * c sia un quadrato e quindi sto descrivendo una soluzione per ogni n. Se n fosse un numero primo, potresti usare Fermat's theorem, per decidere se l'equazione è risolvibile e usarla, come ha fatto notare l'algoritmo Hermite-Serret per trovare le soluzioni se ce ne sono.

Per risolvere il caso in cui n non è primo, è una buona idea usare Gaussian integers. (Gli interi gaussiani sono solo numeri complessi con coefficienti integrali). In particolare si nota che la norma di x + yi è

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

Quindi si deve trovare l'interi di Gauss x + yi la cui norma è n. Poiché la norma è moltiplicativa è sufficiente risolvere questa equazione per i fattori di n e quindi moltiplicare gli interi gaussiani delle equazioni individuali. Lasciatemi fare un esempio. Vogliamo risolvere

65 = x^2 + y^2. 

Ciò equivale a trovare x, y tali che

N(x+yi) = 65 

nel corso degli interi di Gauss. Noi fattore 65 = 5 * 13, quindi usiamo Fermat per notare che sia 5 e 13 può essere rappresentato come somma di due quadrati. Infine, troviamo sia utilizzando la forza bruta del utilizzando l'algoritmo di Hermite-Serret

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

nota, ho lasciato fuori gli interi gaussion 2-i, -2 + i, ecc con coefficienti negativi. Anche queste sono soluzioni.

Quindi possiamo ora moltiplicare queste soluzioni insieme per ottenere

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

e

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

Quindi, si ottiene i due soluzioni

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

Le altre combinazioni esempio con coefficienti negativi devono essere controllati anche. Non danno nuove soluzioni oltre alle permutazioni e ai segni modificati.

---

Per calcolare tutte le soluzioni si potrebbe anche aggiungere che non è necessario calcolare mai c * c. Trovare i fattori di c è tutto ciò che è necessario. Inoltre, poiché a e b sono entrambi più piccoli di c, non succederà che i prodotti di interi gaussiani non siano rappresentabili con i coefficienti integer a 64 bit. Quindi, se si presta attenzione, i numeri a 64 bit sono abbastanza precisi per risolvere il problema. Certo, è sempre più facile usare solo un linguaggio come Python che non ha questo tipo di problemi di overflow.

Answer 2

Potrebbe anche andare per una libreria BigNum.

Per quanto riguarda un modo efficiente di trovare A e B:

Per ogni valore di b (a partire da c-1 e scendendo fino b * b < c * c/2), calcolare c * c - b * b, quindi controlla se è un quadrato perfetto.

Answer 3

Inizia con un valore 1 per ae un valore di c per b.

Confronta c*c - b*b a a*a. Se sono uguali, hai una corrispondenza.

Cambia a e b l'uno verso l'altro a seconda di quale lato è più grande, finché non sono gli stessi.

Answer 4

Dato un c:

Poiché b> a, se a è minimo (a = 1), b = sqrt (c * c - 1).

Pertanto b DEVE essere compreso tra tale valore e c -1.

Inoltre, poiché b deve essere un numero intero, è necessario trovare il primo valore per il quale questo è un numero intero.

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. 

Quindi ci sono esattamente c numeri quadrati in meno rispetto c * c, e si può identificarli utilizzando semplice sottrazione.

Torna all'inizio, prendendo b = sqrt (c c - 1), arrotondando per difetto e tenendo b b, otteniamo la piazza b deve essere al di sopra, e un a = 1. Trovare c c - (a a + b b). Questo dovrebbe darti il ​​numero che deve essere aggiunto per ottenere c * c.

Dal momento che è possibile aggiungere a una 3 + 5 + 7 + ..., e b+2 + b+4 + b+6 + ... ab, devi solo trovare il giusto termine basata sulle somme piuttosto che la piazza stessa :)

Answer 5

Tutte le terne pitagoriche (a, b, c) soddisfare la proprietà che, per alcuni interi k, m ed n,

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

Quindi inizia con il factoring c. Quindi per ogni distinto fattore k di c (cioè per ogni distinto sottoinsieme dei fattori, moltiplicato insieme), trova tutti i m e n che soddisfano c/k = (m^2 + n^2). Fare quest'ultimo richiederà molto meno tempo rispetto all'approccio brute-force che altri hanno suggerito (devi trovare solo i quadrati che sommano a c/k, invece di c^2), ma identificheranno tutti i tripli (a, b, c) . Inoltre non è necessario utilizzare bignums, perché tutti i risultati intermedi si adattano a un lungo.

Suggerisco inoltre di consultare la pagina Web http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html sotto l'intestazione "Un più generale triplo calcolatore pitagorico" che contiene una calcolatrice incorporata, scritta in javascript, che fa esattamente ciò che si desidera.