Az emberek pár ezreléke tudja megoldani ezt a feladványt. Te köztük vagy?

233 =229 + 37 + 17 + 3

ez mintha jó lenne

7² = 49

A 7-nél kisebb prímek: 2, 3, 5; ezeknek a négyzetei: 4, 9, 25; ezeknek együtt kisebb az összege, mint a 49, így biztosan nem írható fel 7² különböző prímek összegeként. 11 esetén ugyanez a helyzet. Tehát első blikkre sem írható fel minden prím négyzete egymástól különböző prímek négyzeteinek összegeként.

~ ~ ~

Közismert, vagy könnyen belátható, hogy minden 3-nál nagyobb prím felírható 6n+1 vagy 6n+5, azaz 6n±1 alakban (6n+0, 6n+2 és 6n+4 osztható lenne kettővel, 6n+3 meg osztható lenne 3-mal).

Mármost:

(6n+1)² = 36n² + 12n + 1 = 6*(6n²+2n) + 1

(6n-1)² = 36n² - 12n + 1 = 6*(6n²-2n) + 1

Ergo minden prím négyzete 6m+1 alakú.

Mivel egy összeg maradéka egyenlő kell, hogy legyen az tagok maradékösszegével, ezért egy prím csak akkor írható fel prímek összegeként, ha az összeg tagjainak száma: 6n+1, mivel gondolom a prím négyzete maga, mint egytagú összeg itt nem játszik, így egy prím négyzete csak 7, 13, 22, stb… darab prímnégyzet összegeként írható csak fel, feltéve, hogy a 2 és a 3 nem szerepel ezen prímek között.

Ha csak a 2 négyzete szerepel az összegben, akkor 6n+4 darab tag kell (2²-et is beleszámolva).

Ha csak a 3 négyzete szerepel az összegben, akkor 6n+5 darab tag kell.

Ha mindkettő szerepel, akkor 6n+2 darab tag kell.

Ha manuálisan keresnék, akkor ezt tudva elvileg könnyebb leszűkíteni a keresést, de nem biztos, hogy egy algoritmus megalkotásánál ez különösebben segítene.

~ ~ ~

Lehetne játszani még azzal is, hogy a 10-zel osztva kapott maradékot elemezgetjük, lévén egy prím négyzete mindig csak 1-re vagy 9-re végződhet, leszámítva 2 és 5 négyzetét, de nem biztos, hogy ez segít.

~ ~ ~

Viszont egy faék egyszerűségű backtrace algoritmussal is észszerű időn belül lehet megoldást találni kisebb prímek esetén. A 10 000-nél kisebb *összes* prímre kb. 1 másodperc alatt lehet eredményt kapni: [link]

Hogy valamilyen analitikus megoldás létezik-e, amit követve akár papírral, számológéppel meg lehetne találni – észszerű időn belül – egy tetszőleges prím esetén ilyen négyzetösszeggel történő felírást? Nem tudom, de sejtésem szerint nem. És bár minél nagyobb egy prím, valószínűleg annál többféle módon lehet felírni, de nem látom garantálva, hogy nincs-e egy olyan nagyobb prím, ami kivétel. Valószínűnek tartom, hogy nincs kivétel, de bizonyítva nem látom. (Kicsit hasonló ez, mint a Goldbach-sejtés.)

De ha van, akkor szabad a gazda…

> Sőt, 24m+1 alakúak, ez kiderül (6n±1)² -ből.

Nem inkább 12m+1 alakúak? (Csak konvergálunk a helyes út felé. :-) )

> "Lehetne játszani még azzal is, hogy a 10-zel osztva kapott maradékot elemezgetjük"

> Ez is fontos lehet bizonyos esetekben:

Az a gond, hogy nem jelent előnyt az, hogy tudjuk, hány prím négyzete kell az összegbe. Hogyan is működik az algoritmusom? Vegyük mondjuk a 300. prímet, ami 1987, pontosabban annak a négyzetét: 3 948 169. Veszi a legnagyobb ennél kisebb prímnégyzetet, ami a 299. prím, a 1979 négyzete, ami 3 916 441. A különbség 31 728, a feladat az, hogy ezt kell felírni prímnégyzetek összegével. Mindjárt csak a √31728 =178,1236 alatti prímek játszhatnak csak, a felbontandó szám rögtön két nagyságrenddel kisebb, és már csak 40 prím áll rendelkezésre az összerakáshoz. A 173-at, a 167-et és a 153-at viszonylag hosszabb kizárni, mert ott tényleg végig kell menni az összes fennmaradó kombináción. De eljutunk 157-ig, aminek a négyzete 24 649, így ami marad az 7079, ami megint egy nagyságrenddel kisebb szám, és immár csak a 84,1367 alatti prímek jöhetnek szóba, amiből már csak 23 darab van. Ebből már relatíve könnyű végignézni az összes kombinációt, ha van megoldás, akkor viszonylag gyorsan ki fogja dobni.

A lényeg, az hogy felülről indulunk a prímnégyzetek elvételével, és a maradékot próbáljuk prímnégyzet összegként felírni. Az, hogy tudjuk, hogy hány tag lehet, az nem segít abban, hogy konkrétan végigvegyük a lehetőségeket és találjunk legalább egyet.

Amúgy lehetne úgy optimalizálni, hogy ha egyszer egy számnál tudjuk a felbontást, akkor azt eltároljuk a memóriában, így mikor egy másik prímnél jutunk erre a számra, akkor már nem kell végigfuttatni az egészet, mert van kész megoldásunk. (Még nem optimalizáltam erre a scriptemet, de ennek akkor van amúgy jelentősége, ha egymás után akarunk több prímnégyzetet így felbontani.) (Meg mivel mostanság javascripttel dolgoztam és most ez áll készhez, így eleve ebben írtam meg, aminek a teljesítménye nem rossz, de messze nem a leghatékonyabb.)

~ ~ ~

Megtettem azt, hogy kizártam azokat a lehetőségeket, amiben a 2² és a 3² szerepel. Így jelentősen lassabb, mert kisebb számoknál van 2²-et vagy 3²-et tartalmazó megoldás, de ilyet tartalmazó megoldás nincs. Így jóval lassabban talál ilyen megoldásokat, illetve több zsákutcának bizonyuló utat kell bejárni, mire megoldást talál. Az első prím, aminél talált olyan megoldást, amiben nincs 2² és 3² sem, az a 311:

311² = 127² + 113² + 107² + 89² + 83² + 79² + 73² + 71² + 67² + 61² + 59² + 53² + 47² + 43² + 41² + 37² + 31² + 29² + 23² + 19² + 17² + 13² + 11² + 7² + 5²

Ha nincs megoldás, akkor minden lehetőséget végigjárva tudjuk csak ezt belátni, a lehetőségek száma meg ha jól érzem, exponenciálisan nő. 4,3 perc kellett, mire a 311-nél kisebb prímek mindegyikén végigjárta az összes kombinációt, hogy kiderüljön, nincs megoldása. 311 esetén is 95 másodperc kellett, mire talált egy megoldást, miután a 127 és 311 közötti prímeknél végigjárta az összes zsákutcát.

A következő prímre nincs megoldás, utána még 3–4-nél megvártam és volt megoldás. Aztán inkább leállítottam a scriptet.

~ ~ ~

> megkérnélek hogy nagyobb prímekre (mondjuk pl. 10^6, vagy 10^7 közelében) is futtasd le néhányra, úgy, hogy csak 3-nál nagyobb különböző prímeket engedünk meg.

Majd később ránézek, de fene tudja mennyire lesz reménytelen. Előbb megnézem a hatjegyű prímekig bezárólag, hogy mindegyiknél van-e megoldás a kötöttség nélkül – borítékolnám, hogy van –, és az úgy mennyi ideig tart.