A válasz az életre, az univerzumra és mindenre
Az MIT Andrew Sutherland és Andrew Booker (Bristoli Egyetem) által vezetett csapat megoldotta egy 65 éves híres matematikai rejtvény utolsó darabját, és megtalálta a választ a legnehezebben megfejthető számra: a 42-re.
A 42-es szám különösen fontos Douglas Adams sci-fi író “Útikalauz stopposoknak a galaxisba” című regényének rajongói számára, mivel ez a szám a válasz, amelyet egy szuperszámítógép adott “az élet, az univerzum és minden végső kérdésére”.
Booker a 42-re adott válaszra is kíváncsi volt. Azaz, van-e három olyan kocka, amelynek összege 42?
Ez a három kocka összege rejtvény, amelyet először 1954-ben állítottak fel a Cambridge-i Egyetemen, és amely az x3+y3+z3=k diofantikus egyenlet néven ismert, kihívás elé állította a matematikusokat, hogy 1-100 számra találjanak megoldást. Kisebb számok esetén az ilyen típusú egyenletet könnyebb megoldani: például a 29-et fel lehet írni 33+13+13-nak, míg a 32 megoldhatatlan. Két szám kivételével végül mindegyiket sikerült megoldani, vagy megoldhatatlannak bizonyítani különböző technikák és szuperszámítógépek segítségével:
Booker egy zseniális algoritmust dolgozott ki, és heteket töltött az egyetemi szuperszámítógépén, amikor nemrég előállt a 33-as szám megoldásával. Amikor azonban a 42 megoldásához fordult, Booker rájött, hogy a számítási igény egy nagyságrenddel nagyobb, és talán meghaladja a szuperszámítógép képességeit. Booker elmondása szerint számos felajánlást kapott a megoldás megtalálásához, de ehelyett barátjához, Andrew “Drew” Sutherlandhez, a Matematikai Tanszék vezető kutatójához fordult. “Ő a világ szakértője az ilyesmiben” – mondja Booker.
Sutherland, akinek a szakterülete a tömegesen párhuzamos számítások, 2017-ben megdöntötte a legnagyobb Compute Engine fürt rekordját, 580 000 maggal a Preemptible Virtual Machines-en, a legnagyobb ismert, nyilvános felhőben futó nagy teljesítményű számítási fürtön.
A többi számelméleti számelméleti szakemberhez hasonlóan, akik aritmetikai geometriával foglalkoznak, tisztában volt a “három kocka összege” problémával. És ők ketten már korábban is dolgoztak együtt, segítettek az L-functions and Modular Forms Database (LMFDB), az úgynevezett Langlands-programhoz kapcsolódó matematikai objektumok online atlaszának létrehozásában. “Nagyon megörültem, amikor Andy megkért, hogy csatlakozzam hozzá ebben a projektben” – mondja Sutherland.
Booker és Sutherland megvitatták a 42 megoldásának keresése során alkalmazandó algoritmikus stratégiát. Ahogy Booker a 33-as megoldásánál is rájött, tudták, hogy nem kell az x, y és z összes lehetőségének kipróbálásához folyamodniuk.
“Van egyetlen egész szám paraméter, d, amely meghatározza az x, y és z lehetőségek viszonylag kis halmazát úgy, hogy a z abszolút értéke egy választott B keresési korlát alatt legyen” – mondja Sutherland. “Ezután felsoroljuk a d értékeit, és ellenőrizzük a d-hez tartozó minden egyes lehetséges x, y, z-t. A 33 feltörésére tett kísérlet során a B keresési korlát 1016 volt, de ez a B túl kicsinek bizonyult a 42 feltöréséhez; helyette B = 1017-et használtunk (1017 100 millió milliárd).”
A 33 és a 42 keresése között egyébként a fő különbség a keresés mérete és a használt számítógépes platform lenne. A brit székhelyű Charity Engine nagylelkű felajánlásának köszönhetően Booker és Sutherland több mint 400 000 önkéntes otthoni számítógépének számítási teljesítményét tudta megcsapolni a világ minden tájáról, amelyek mindegyikéhez különböző d értékeket rendeltek. A számítás minden egyes PC-n a háttérben fut, így a tulajdonos továbbra is használhatja a számítógépét más feladatokra.
Sutherland Douglas Adams rajongója is, így a projekt ellenállhatatlan volt.
A Charity Engine használatának módszere hasonlít a “Stopposok” című regényben a 42-es szám körüli cselekmény egy részéhez: Miután a Deep Thought 42-es válasza nem bizonyul kielégítőnek a tudósok számára, akik nem tudják, hogy milyen kérdésre hivatott válaszolni, a szuperszámítógép úgy dönt, hogy a Végső Kérdést úgy számítja ki, hogy a Föld által működtetett szuperszámítógépet épít … más szóval, egy világméretű, tömegesen párhuzamos számítási platformot alkalmaz.
“Ez a másik ok, amiért nagyon szerettem ezt a számítást a Charity Engine-en futtatni – valóban egy bolygóméretű számítógépet használtunk egy régóta nyitott kérdés megoldására, amelynek válasza 42.”
Egy sor számítást futtattak alacsonyabb kapacitáson, hogy teszteljék mind a kódjukat, mind a Charity Engine hálózatát. Ezután számos optimalizációt és adaptációt alkalmaztak, hogy a kódot jobban alkalmassá tegyék egy tömegesen elosztott számításhoz, mint egy egyetlen szuperszámítógépen futtatott számításhoz – mondja Sutherland.
Miért nem tudta a bristoli szuperszámítógép megoldani ezt a problémát?
“Nos, bármelyik számítógép *megoldhatja* a problémát, feltéve, hogy hajlandóak vagyunk elég sokáig várni, de mivel nagyjából félmillió számítógép dolgozott párhuzamosan a problémán (mindegyik több maggal), sokkal gyorsabban tudtuk elvégezni a számítást, mint ahogy azt a bristoli gép (vagy bármelyik gép itt az MIT-n) segítségével meg tudtuk volna tenni” – mondja Sutherland.
A Charity Engine hálózatának használata energiatakarékosabb is. “Többnyire olyan számítási erőforrásokat használunk, amelyek egyébként kárba vesznének” – mondja Sutherland. “Amikor a számítógépünk előtt ülve olvasunk egy e-mailt vagy dolgozunk egy táblázatkezelőn, a rendelkezésre álló CPU-erőforrásnak csak egy parányi töredékét használjuk, és a Charity Engine alkalmazás, amely a Berkeley Open Infrastructure for Network Computing (BOINC) rendszeren alapul, ezt kihasználja. Ennek eredményeként ennek a számításnak a szénlábnyoma – ami azzal az elektromos árammal kapcsolatos, amelyet a számításaink miatt a hálózatban lévő PC-k azon felül használtak, amit egyébként is használtak volna – alacsonyabb, mintha szuperszámítógépet használtunk volna.”
Sutherland és Booker több hónapon keresztül futtatta a számításokat, de a végső sikeres futtatást mindössze néhány hét alatt végezték el. Amikor megérkezett az e-mail a Charity Engine-től, az x3+y3+z3=42 első megoldását közölte:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
“Amikor meghallottam a hírt, határozottan ökölcsapás volt” – mondja Sutherland. “Ezeknél a nagyméretű számításoknál rengeteg időt és energiát fektetünk a megvalósítás optimalizálásába, a paraméterek finomhangolásába, majd heteken és hónapokon át teszteljük és újra teszteljük a kódot, és soha nem tudhatjuk, hogy az összes erőfeszítés megtérül-e. Ezért rendkívül kielégítő, amikor ez megtörténik.”
Booker és Sutherland szerint még 10 számot kell megoldani, 101-1000 között, a következő szám a 114 lesz.
De mindkettőjüket jobban érdekli egy egyszerűbb, de számítási szempontból nagyobb kihívást jelentő rejtvény: hogy van-e több válasz a három kocka összegére a 3-ra.
“Van négy nagyon egyszerű megoldás, amit már ismert Louis J. Sutherland matematikus. Mordell, aki 1953-ban azt írta: “Semmit sem tudok az x3 + y3 + z3 = 3 egész számú megoldásairól azon túl, hogy létezik a négy hármas (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4); és valóban nagyon nehéz lehet bármit is kideríteni bármilyen más megoldásról. Ez az idézet motiválta a három kocka összege probléma iránti érdeklődést, és különösen a k=3 esetet. Bár feltételezhető, hogy végtelen sok megoldásnak kellene léteznie, a több mint 65 éves kutatás ellenére csak azokat a könnyű megoldásokat ismerjük, amelyeket már Mordell is ismert. Nagyon izgalmas lenne egy újabb megoldást találni k=3 esetén.”