Už šio uždavinio sprendimą – šimtai tūkstančių eurų

Šiandien Vilniaus universiteto Matematikos ir informatikos instituto mokslo darbuotojas docentas matematikos daktaras Igoris Belovas skaitytojams siūlo susipažinti ketvirtąja, paskutine sąrašo problema – Eulerio galvosūkiu apie beveik kvadratinius pirminius skaičius.

Dalijamės matematiko pastebėjimais.

Ar kvadratinių pirminių skaičių yra be galo daug?

Šveicarų kilmės matematiko, daug metų dirbusio Sankt-Peterburge, Leonardo Eulerio vardas yra susijęs ne tik su pirmąja Landau problema – Goldbacho hipoteze (1742 m). Po keliolikos metų, 1760 m., jis iškėlė klausimą: ar beveik kvadratinių pirminių skaičių yra be galo daug?

Priminsime, kad skaičius q vadinamas beveik kvadratiniu, jei jis skiriasi vienetu nuo kokio nors sveikojo skaičiaus kvadrato, t.y., beveik kvadratinis skaičius užrašomas pavidalais q = n2+1 arba q = n2-1, čia n yra koks nors sveikasis skaičius.

Pabandykite savarankiškai nustatyti, ar pirminių pavidalo n2-1 yra be galo daug, o mes pasigilinsime, kiek yra pirminių pavidalo n2+1 (žr. paaiškinimus straipsnio pabaigoje).

Pirminių skaičių lentelė

Sudarykime lentelę, surinkdami visus tokius pirminius:

Ši seka turi labai įdomių savybių, susijusių su liekanomis. Padalinkime skaičius antroje lentelės eilutėje iš 4, iš 10, iš 20 ir užrašykime gautas liekanas. Padalinkime skaičius antroje lentelės eilutėje iš 4, iš 10, iš 20 ir užrašykime gautas liekanas.

Ką gi matome?

Galima pastebėti:

1) pradedant nuo 5, q dalijasi iš 4 su liekana 1;

2) pradedant nuo 17, q dalijasi iš 10 su liekanomis 1 arba 7;

3) pradedant nuo 17, q dalijasi iš 20 su liekanomis 1 arba 17.

O dabar pabandykite įrodyti šiuos teiginius visiems beveik kvadratiniams pirminiams.

Beje, Euleris pateikė savo hipotezę ir taip: ar pirminių skaičių pavidalo xy+z, kur x, y ir z yra iš eilės einantys natūralieji skaičiai, yra be galo daug? Pabandykite irgi savarankiškai įsitikinti, ar abi formuluotės yra ekvivalenčios. Paaiškinimai straipsnelio pabaigoje.

Hipotezės ir eksperimentai

Nors ketvirtoji Landau problema dar nėra išspręsta, tačiau pavyko rasti labai panašių problemų sprendimus, kurie suteikia viltį išspręsti ir beveik kvadratinių pirminių galvosūkį.

Lenkų matematikas Henrikas Ivaniec 1978 m. įrodė, kad yra be galo daug beveik kvadratinių skaičių, kurie yra pirminiai arba bent dviejų pirminių sandauga. Vėliau, 1997 m., jis kartu su kanadiečiu Dž. Fridlenderiu įrodė, kad yra be galo daug pirminių skaičių pavidalo n2+m4. Už savo pasiekimus skaičių teorijoje H. Ivaniec 2001 m. buvo apdovanotas tarptautine Ostrovskio premija (100 000 Šveicarijos frankų) bei daugeliu kitų prizų.

Pasinaudojus Bruno sietu pavyko įrodyti, kad beveik kvadratinių pirminių, neviršijančių duoto realaus skaičiaus x, yra ne daugiau nei santykis √x/log(x), padaugintas iš tam tikros konstantos.

Britų matematikai G. Hardi ir Dž. Litlvudas jau 1922 m. spėjo, kad beveik kvadratinių pirminių, neviršijančių duoto skaičiaus x, kiekis πq(x) yra apytikriai lygus A(x)=Cq∙√x/log(x). Čia Cq ≈1.372813462818246009112192696727… Visai neseniai, 2008 m., M. Volfas pasiūlė sudėtingesnę formulę. Skaičiavimai rodo, kad jo pasiūlyta formulė B(x) yra pastebimai artimesnė πq(x) negu A(x):

Dar geriau tai parodo priklausomybių grafikai:

Jei skaitiniai eksperimentai patvirtina iškeltas hipotezes, tai, galbūt, beveik kvadratinių pirminių yra be galo daug? Deja, šie skaičiavimai teorinio įrodymo nesuteikia, tačiau gali daug pagelbėti jo beieškant.

Kol teoretikai tiria neaprėžtai didelių pirminių savybes, skaičiuotojai pirminių skaičių paieškai pasitelkia kompiuterius ir paskirstytus skaičiavimus. Kompiuteriniai skaičiavimai leido jau nustatyti, kad yra beveik kvadratinių pirminių skaičių, didesnių už 10^19. Tačiau ar yra tokių skaičių, didesnių už 10^21 ar 10^25?

Siūlo prisidėti prie projektų

Siekiant suvienyti pastangas bei išteklius skaičiavimams, kuriamos viešųjų paskirstytų skaičiavimų (public computing) sistemos, kuriose gali dalyvauti visi norintys prisidėti prie pirminių skaičių ar kitokių mokslo skaičiuojamųjų projektų.

Yra plačiai žinomas pirminių skaičių paieškos projektas „PrimeGrid“, sukurtas Berklio universiteto BOINC platformos pagrindu, prie kurio visi pageidaujantys gali prisijungti su savo kompiuteriais per nesudėtingą prieigą internete ir tapti projekto dalyviais. Projekto dalyviai gali patys atlikti tam tikras užduotis arba paskirti savo kompiuterio išteklius projekto skaičiavimams atlikti.

Pažymėtina, kad BOINC platforma leidžia tas užduotis atlikti nesutrikdant įprasto kompiuterio darbo ir pajungiant jį projekto skaičiavimams tik tada, kai jis būna neužimtas jokiomis užduotimis.

Priklausomai nuo atliktų užduočių sudėtingumo projekto dalyvis yra apdovanojamas 18 lygių ženkleliais, kintančiais nuo bronzinio iki dvigubo smaragdinio. Paprasčiausią ženklelį galima gauti per dieną, o aukštesnio lygio įvertinimui pasiekti reikia skirti daugiau laiko ir kompiuterio išteklių.

Siūlo piniginius prizus

Tie, kuriems pavyksta atrasti naują rekordiškai ilgą pirminį skaičių, patenka į Chriso Caldwello „Didžiausių žinomų pirminių duomenų bazę“ ir gauna Pirminių Titano titulą. Kitas „PrimeGrid“ tikslas yra pateikti medžiagą bei gilesnes žinias apie pirminius skaičius.

Pagaliau, kadangi pirminiai skaičiai sudaro kompiuterių saugos kriptografinių sistemų pagrindą, jų savybių studijavimas „Primegrid“, pavyzdžiui, leidžia įvertinti, kiek reikia atlikti skaičiavimų, norint „nulaužti“ vieną ar kitą kodą ir tokiu būdu įvertinti kompiuterio kriptografinės sistemos saugumą.

Savo ruožtu EEF (Electronic Frontier Foundation) paskelbė apie piniginius prizus, įteikiamus už labai didelių pirminių skaičių radimą. 50 tūkst. dolerių prizą už milijono skaitmenų ilgio pirminio radimą 2000 m. laimėjo Nayan Hajratwala iš Mičigano (JAV), savo rekordui pasiekti pasinaudojęs dešimčių tūkstančių kompiuterių, sujungtų į tinklą Entropia.com, galia.

Kitas EEF 100 tūkst. dolerių prizas už 10 000 000 skaitmenų ilgio pirminio radimą buvo įteiktas 2009 m. Už 100 000 000 skaitmenų ilgio pirminio radimą yra paskelbtas 150 tūkst. dolerių (134 tūkst. eurų), o už 1 000 000 000 skaitmenų ilgio pirminio radimą - 250 tūkst. dolerių (223 tūkst. eurų) prizas, kurie dar laukia savo laimėtojų.

Uždavinių sprendimų paaiškinimai

Kadangi beveik kvadratinis skaičius pavidalo n2 - 1=(n -1)∙(n +1) yra išreiškiamas sandauga, nesunku pastebėti, jog šitoks pirminis yra tik vienas: 3=(2 - 1)∙(2 +1).

Teiginys apie dalumą iš 4 kyla iš to, kad tam, kad qn būtų nelyginis skaičius (pirminiai, išskyrus 2, yra nelyginiai), n turi būti lyginis, taigi n2 dalijasi iš 4.

Teiginys apie dalumą iš 10 kyla iš to, kad lyginio skaičiaus kvadratas baigiasi 0, 4 arba 6. Tačiau n2 negali baigtis 4, nes šiuo atveju n2+1 dalintųsi iš 5. Teiginys apie dalumą iš 20 yra šiek tiek sudėtingesnis. Skaičius q yra pirminis, taigi liekana turi būti nelyginė, ir nesidalinti iš 5, nes kitaip q nebūtų pirminis. Tačiau liekana negali turėti pavidalą 4m+3, t. y. įgyti reikšmes 3, 7, 11 arba 19, nes 4k2 ≠ 20l+(4m+2). Liekana negali būti lygi 9, nes k2 ≠ 5l+2. Liekana negali būti lygi 13, nes k2 ≠ 5l+3, juk nenulinės liekanos nuo kvadrato dalybos iš 5 yra 1 ir 4. Taigi, galimos liekanos tik 1 ir 17.

Abi Eulerio formuluotės yra ekvivalenčios. Tuo nesunku įsitikinti, paėmus x = n - 1, y=n , z=n +1.