Segítesz egy "mind négyzetszám legyen" feladatban?

b+c=u^2

b-c=v^2

b=(u^2+v^2)/2

c=(u^2-v^2)/2 és így tovább

Írtam rá programot, ez jött ki:

434657 + 420968 + 150568 = 1006193

434657 + 420968 = 855625 = 925^2

434657 - 420968 = 13689 = 117^2

420968 + 150568 = 571536 = 756^2

420968 - 150568 = 270400 = 520^2

434657 + 150568 = 585225 = 765^2

434657 - 150568 = 284089 = 533^2

(Nem biztos, hogy ez a legkisebb összeg.)

A brute force nagyon lassú lenne, de kiegészítve azzal a trükkel, amit #1 is mondott, már elég gyors.

Szóval 3 egymásba ágyazott ciklusom van:

- a külső az a+b = u² négyzetszámokon megy sorban (lehet kicsit itt is trükközni, hogy (u+1)² = u² + 2u+1)

- a második az a-b = v² négyzetszámokon (amik azonos paritásúak u²-tel, vagyis 1-ről vagy 4-ről indulnak és csak minden második négyzetszámot kell nézni, (v+2)² = v² + 4v+4. A leállító feltétel pedig v² < u² lesz.). Ezekből kijön a és b.

- a harmadik ciklus a b-c = w² négyzetszámokon megy végig 1-től w² < b-ig. Ez kiadja c-t.

Többet már nem lehet gyorsítani, most már brutálisan ellenőrizni kell a b+c, a+c és a-c négyzetszám voltát.

Ez a legkisebb a+b-hez tartozó számhármast találja meg elsőre, tehát elméletileg lehet, hogy a+b+c-re van nála kisebb is egy nagyobb a+b-nél, ezért tovább kell menni a kereséssel (u² = a+b < a₁+b₁+c₁-ig).