Combinazioni di tre numeri positivi x, y, z in modo che x + y, x - y, y + z, y - z, x + z e x - z siano quadrati perfetti

Question

Buongiorno, sono nuovo qui e Io porto un piccolo problema. Sto avendo problemi a sviluppare un algoritmo efficiente per il seguente problema: Ho bisogno di trovare combinazioni di tre numeri positivi x, yez in modo che x + y, x - y, y + z, y - z, x + z e x - z sono quadrati perfetti. Il problema è sviluppare un algoritmo che trovi tutte le combinazioni di x, yez tra 1 e 2.000.000.

Attualmente utilizzo uno for all'interno di uno for che sicuramente non finirà prima di avere i miei nipoti.

Answer 1

L'idea di base per iniziare con una sostituzione, come:

u = x + y 
v = x - y 
w = y + z 

Poi x + y, x - y, y + z, y - z, x + z e x - z diventa

u, v, w, u - v - w, v + w, u - w [all have to be squares] 

Poi, con un'altra sostituzione, u = a², v = b², w = c², si ottiene:

a², b², c², a² - b² - c², b² + c², a² - c² [all have to be squares] 

ora è possibile enumerare tutti a, b, cs che può già essere veloce e nough.

Ulteriori idee potrebbero essere enumerare prima tutti i b², c², b² + c² utilizzando Pythagorean triples (sostituendolo a m e n, enumerando tutto coprime (m, n) e quindi utilizzando la formula Euclid) e quindi trovare per dato (b, c) come in un modo simile (ad esempio, cambiare a² - c² = x² in a² = x² + c² e utilizzare di nuovo le triple).

Answer 2

estensione BeniBela's answer,

x + y = (x - z) + (y + z) 
x + y = (x + z) + (y - z) 

Quindi, triplette sono valide solo se l'ipotenusa può essere rappresentato in due forme diverse. Un ulteriore filtraggio può essere fatto osservando che (x - z) e (x + z) formano anche l'ipotenusa di una tripletta pitagorica.