Melyik az a 32-nél nagyobb, legkisebb pozitív egész szám, amelyik nem írható fel legfeljebb 7 prímszám-négyzet összegeként?

Egymillióig megnéztem, és nincs olyan, amihez 8-nál több kéne. Ami meglepő, hogy az első egymillió számhoz átlagosan 5.5 prímnégyzet kell, és közel 3%-ukhoz 8. Ez azért lepett meg, mert nagyon sok szám "centizi ki" a dolgot, de mégsem kellett egyikhez sem 9 tag.

Azért nagy összegben nem fogadnék, hogy mondjuk egymilliárd számot megnézve se találnánk ilyet. Főleg, mivel a mozgó átlag lassan de biztosan kúszik felfelé. Százezrenként: 5.40, 5.49, 5.52, ..., 5.57, 5.58

Rácuppantam erre a kérdésre. Megdöbbentőnek tartom, hogy az 1/2/3/4/5/6/7/8 darab prímnégyzetből felírható számok sűrűsége aszimptotikusan konvergensnek tűnik.

Ez azért érdekes, mert a(n) = min(a(n-p^2)) + 1, ahol p a gyök(n)-ig futó prímek halmaza. Tehát egy nagy n-hez kipróbálhatok egy csomó n-p^2-et, és mégis folyton előfordul, hogy az összeshez magas érték tartozik. Magyarán az a(n) sorozat igen erősen strukturált.

Megnéztem ennek a legextrémebb példányait, azaz a pontosan 8 prímszám-négyzet összegeként felírható számokat. Ez nem ritka dolog, a számok több mint 3%-a ilyen, bármilyen magasra is megyek. Vegyük például az 1000035-öt. Ehhez a számhoz kipróbálhatok 168 darab prímet 2-től 997-ig terjedően, és mégis, mind a 168 a(1000035 - p^2) értéke kereken 7! Nem tudom 8-nál kevesebb prímnégyzetből előállítani, pedig 168 különböző lehetőségem lett volna rá. De mindegyikkel pontosan 8 tag szükséges, se több, se kevesebb. Ez mennyire durva már...

Egy érdekes mintázatot felfedeztem: a 8 prímnégyzet összegeként felírható számok 99.8%-a (legalábbis az első négymillió körében) 120-ra nézve 75/83/91/92/96/97 maradékot ad, mégpedig egyenlő arányban, és többnyire csomósodva. Példa: 1000035, 1000043, 1000051, 1000052, 1000056, 1000057. A fenti hat maradékosztály pontosan a számok 5%-át fedi le, és a számok több mint 3%-a 8 prímnégyzetből áll. Tehát ha a hasamra ütök, és választok egy tetszőleges 120-ra 75 maradékot adó számot, akkor több mint 60% esélye lesz, hogy pontosan 8 prímnégyzet összegéből álljon elő.

Sőt, az egyes maradékosztályok viselkedése is eltér. A 75-ösbe tartozók előállítása ha nem 8 tagú, akkor szinte mindig 3. A 83-asé 5, a 91/96-osé 7, a 92/97-esé 6. Én csak egy hobbista vagyok, és tátom a számat, de egy rendes matematikus biztos rá tudna jönni, mi ez az egész.

Nem fejezted be a listát, de ha minden igaz, akkor szerinted a következő (mod 24) esetek nehezek: 1, 2, 4, 12, 20, 21. Ezeknél marad csak 4 kombinálható NP-nk a kettesekkel és hármasokkal való kiegyenlítgetés után. Teljesen igazad van abban, hogy ezek a valódi nehéz esetek, nem pedig azok, amikhez mind a 8 tag kell. Hiszen pl. a 2 (mod 24) vagy a 21 (mod 24) számokhoz nem azért nem szükséges 8 tag mert olyan könnyűek hogy kevesebből is kijön, hanem mert 8 tagból soha nem is lehetne őket megcsinálni.

Mostmár azt is látom, hogy az én 75 (mod 120)-as kategóriám miért vagy 8, vagy 3 tagból jön ki (illetve sokkal-sokkal ritkábban 7 vagy 4 tagból): 3 (mod 24)-hez 5*NP+9+9+4 vagy 3*NP kell, esetleg a brutál ritka 2*NP+9+4+4+4+4 vagy 1*NP+9+9+4+4. Bár azt azért megjegyezném, hogy hiába tűnik nagyon nehéznek a 3*NP, azért mégis összejön a 75 (mod 120) számok több mint 30%-ára.

Én abba az irányba indulnék el innen, hogy mekkora valószínűséggel keverhető ki egy tetszőleges n nagyságrendű érték 4 darab a prímnégyzetek ritkaságát követő számhalmazból. Ilyenkor elszakad az ember a konkrét prímektől, maradékoktól, és azt mondja, hogy a prímek sűrűsége 1/log(x), abból a prímnégyzetek sűrűsége mittudomén mennyi, ezekből 4-et kombinálva egy adott intervallumba y számot lehet csinálni, y sokkal nagyobb mint az intervallum hossza, annak az esélye hogy egy konkrét számra ebben az intervallumban egy kombináció se landoljon iszonyú kicsi, kiintegrálod a már ismert egymilliárdtól a végtelenig, és ha az még mindig kicsi, akkor a sejtés erős.

Van például a Goldbach-sejtés (minden páros szám 2 prím összege) amit senki nem tudott még bizonyítani, pedig nevetségesen sokféleképpen lehet minden nagy számot prímek összegeként felírni, és a valószínűsége hogy mégis legyen egy olyan amit nem lehet, kisebb annál minthogy a kommentem elküldése után spontán New Yorkba teleportálok. Úgyhogy a legjobb amit tenni tudtak eddig, probabilisztikusan megbecsülték hogy hány ilyen szám lehet, és kijött hogy 0.0000000000...0000001.

Ideskiccelem a heurisztikus becslést. A nehéz esetekben a kiegyensúlyozás után az a célod hogy kirakj 4 prímnégyzetből egy jól meghatározott 4 (mod 24) számot. Legyen ennek a célszámnak a nagyságrendje n.

Az összeghez az 5-től √n-ig terjedő prímeket használhatod, ezekből van kb. √n / ln(√n). Ezekből hány négyes kombináció készíthető? Durván a negyedik hatvány osztva 4!-al, azaz n^2 / (4! ln^4(√n)). Milyen értéktartományban mozognak ezek a 4 tagú prímnégyzetösszegek? 100-tól 4n-ig. Nyilván nem egyenletes eloszlással, de bennünket a sűrűsége n körül érdekel, ami kellően középen van ahhoz, hogy én most idő hiányában ráfogjam, hogy a kombinációk számának és az értéktartomány méretének hányadosa jó becslés rá. (gyors szimuláció n = 64 millióra, 8000 alatti prímekből képzett négyes négyzetösszegek eloszlása: [link] - n a csúcson van, az átlag még szolid becslés is rá)

Az összegről tudjuk még, hogy 4 (mod 24), tehát minden elem a 4n kalap minden 24-edikébe esik, így az értéktartomány 4n / 24 = n/6 elemszámú.

A kombinációk és az ÉT elemszámának hányadosa (n^2 / (4! ln^4(√n))) / (n/6) = n / (4 ln^4(√n)). Ez n=10^9-re már 21700. Az ekkora számokat tehát nagyon-nagyon sokféleképpen lehet kirakni 4 prímnégyzet összegéből. A rend kedvéért érdemes lenne kisebb, mondjuk milliós nagyságrendű számokra megnézni, hogy jól működik-e a modell, és legalább lokálisan nagyjából lapos-e a működő kombinációk számát leíró függvény. Ideális esetben azt látod, hogy jó a modell, és az egyes számokhoz működő kombinációk száma Poisson jellegű.

Ha nem nagyon szar a modell, akkor erre már azt mondja az ember, hogy nincs értelme folytatni, a sejtés erős, olyan jellegű mint a Goldbach. Csak szemléltetésnek, ha a Poisson és a legalább 21700+ kombináció stimmel, akkor a nulla lehetséges kombináció valószínűsége √21700 = 147 szigmás esemény, teljesen abszurd. Ilyenekkel már nincs értelme tovább számolgatni. Igen, végtelen sok szám létezik, de az egyre nagyobbakhoz még egyre extrémebb szigmák tartoznak, és akinek van egy kis tapasztalata az ilyen jellegű problémákkal, tudja, hogy ebből egy szinte nullás várható érték jön ki a végtelenig szummázva is. Először még megcsinálja az ember, de én már nem fogom, mert tudom hogy így van.

Na, még egy utolsó kép: 300-315 ezer közötti 4 mod (24) számok hányféle négytagú prímnégyzet összegéből állhatnak elő [link]

Azért 300 ezer környékét mutatom, mert csak az első 100 prímet kombináltam ki izomból.

Az eloszlásuk nem Poisson, hanem valamilyen érdekes bimodális eloszlás. De a lényeg, hogy az alsó része még mindig bőven elég magasan fut, hogy az okfejtés megálljon a lábán. Ehhez az n=300000-es nagyságrendhez amúgy a n / (4 ln^4(√n)) képlet 47-et ad, ami tök jó! Megnéztem 50, 100, 200 ezerre is, és azoknál is épp annyi, mint ahol a pontok legalja fut. Elégedett vagyok, és mostmár el tudom engedni ezt a kérdést :)

Nem bírok magammal, 2 millió környéke: [link] a becslés 180, ez is jó. De ami igazán érdekes, az eloszlás nem bimodális, hanem 5 részből tevődik össze, kettő az alsó sávot adja, a másik 3 a felsőt. Szétszedtem őket n mod 5 szerint, és a jobb láthatóság, tiszta elkülönítés kedvéért sorbarendeztem az egyes osztályok értékeit: [link] Nagyon állat. Meg lehetne nézni, hogy az egyes osztályokra milyen kombinációk jellemzőek, tehát a legalsó, átlagosan 250 körüli kombinációkban milyen mintázatok vannak, a felső 1500 miben más, stb. Ez alapján talán egzaktabbul is le lehetne írni az egyes osztályok n-től és n mod 5-től függő eloszlását.

Ami egészen biztos, hogy egyenként sem Poisson-ok: a szórásuk a várható érték hetede, nem pedig négyzetgyöke, ami nagyon nem mindegy. Ugyanakkor mindegyiknek pozitív a ferdesége és negatív a kurtózisa, így extrém alacsony értékek produkálására ugyanúgy egyre képtelenebbek.

Tök jó hogy ezt a kérdést kiírtad, remekül elszórakoztam vele. Az időzítés tökéletes, szinte semmi munkám nem volt a héten, de mivel ehhez a feladathoz programozgatok meg excelezek, távolról még úgy is nézett ki, mintha dolgoznék. Na de itt a hétvége, úgyhogy isten veled addig is. Ha találsz valami érdekeset, feltétlen írd be.