Hogyan oldható meg az a*a + b*b + c*c + d*d = E egyenlet? Minden szimbólum nem negatív egész számot jelent.

Hirtelen ezt találtam a témában:

[link] math.colgate.edu/~integers/sjs15/sjs15.pdf

Általánosan ezek szerint nem triviális.

Nem oldható meg. Vannak számok, amelyekre nincs megoldás, például a 33 ilyen. Egy egyszerű algoritmus a következő. Adott egy szám, megkeresed a nála kisebb legnagyobb négyzetszámot, a maradékra ugyanezt még háromszor. Lesznek számok, amelyekre lesz további maradék, ezekre az állítás nem igaz, a többire pedig ez megoldás.

Például 1001. 31*31=961, maradt 40. 6*6=36, maradt 4. 2*2=4. a negyedik 0*0.

Azaz 4 lépés mindig eredményt ad.

@09:37

Ahogy írod mindig a nála kisebb legnagyobb négyzetszámot keresed, egy mohó algoritmus amiről nem vagyok meggyőződve, hogy minden esetben talál megoldást, ha létezik.

Nekem nem triviális hogy van e olyan nemnegatív egész szám amire nem létezne megoldás.

Megoldások 33-ra :

33 = 0*0 + 1*1 + 4*4 + 4*4

33 = 0*0 + 2*2 + 2*2 + 5*5

33 = 2*2 + 2*2 + 3*3 + 4*4

09:37,

33 --> 25, 8 --> 4, 4 --> 4, 0 --> 0,

tehát 33 = 5^2 + 2^2 + 2^2 + 0^2.

Nem elég, hogy a 33-ra van megoldás, hanem egyenesen a te algoritmusod adja.

Ha csak elírás, és a 43-ra gondolsz, az valóban példa arra, hogy ez az algoritmus nem működik:

43 --> 36, 7 --> 4, 3 --> 1, 2 --> 1; és itt valóban kéne egy 5., de próbáld ki, hogy

43 = 5^2 + 3^2 + 3^2 + 0^2.

Ha elolvasod az első válasz linkjén az Introduction első mondatát, akkor egy nagyon érdekes új tételt tanulhatsz majd belőle.

Amúgy az O(log(E)^2)-es megoldás elég gyors (még úgy is, hogy nem a szükséges bitműveleteket számolja, hanem a sima aritmetikai műveleteket). Annyi szépséghibája van, hogy egy ponton véletlen számokat használ – ami valamilyen szempontból lehet, hogy találgatásnak minősül – de szupergyorsan eredményre vezet.

Persze lehet, hogy vannak véletlen számokat nélkülöző algoritmusok is, amik mindig eredményre vezetnek, legfeljebb kicsit több számolással. (Persze ott is kérdés, hogy a próbálgatás az mennyire „találgatás”, mert például egy triviális ilyen algoritmus, hogy végig megyünk az összes, (E + 1)^4 darab számnégyesen. Ebben nincs véletlen szám, és tutira megadja az összes megoldást az egyenletre.)

Találtam ilyen algoritmust : [link]

Szúrta a szememet, hogy adott n-re kiszámolva mindig legenerálná az Eratoszthenész szitáját, sőt egyáltalán hogy kell az hozzá (nem szükséges).

Prímtényezőkre bontás után, a prímtényezőivel operál.

Egy a triviálisnál gyorsabb futási idejű prímtényezőkre bontó a Pollard's rho algortimus nagy számokra, de én a wheel algoritmust használtam ...

Íme a kód amit összeraktam mások kódjait újrafelhasználva : [link]

Instant kipróbálható változat :

[link]