článek o prvočíslech - Prime Grid

Debaty o všem co se týká týmových stránek a fóra Czech National Team.

Moderátoři: petnek, nenym, Zelvuska

Odpovědět
Zpráva
Autor
Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

článek o prvočíslech - Prime Grid

#1 Příspěvek od forest » pát 10 led, 2020 12:42

Pokud by někdo chtě pomoci s přípravou článku o prvočíslech, potažmo projektu PG a jeho podprojektech, tak mi prosím písněte.
Zatím se na toto téma vrhla má čerstvě třináctiletá dcera, takže jí s tím v rámci možností budu muset pomoct. Nějaký odborník, případně nadšenec do prvočísel, by se ale do přípravného týmu hodil, aby mělo výsledné dílo co nejlepší kvalitu.
Tento článek mně již léta na našem webu schází, tak snad se jej podaří během pár měsíců dát dohromady a na web.

Druhá dcera se již před létními prázdninami vrhla na Enigmu, ale ta po měsíci přestala dávat práci a veškerá snaha se tedy díky tomu zastavila. To téma ji zaujalo po nějakém dokumentu v TV. Dokud nebude jisté, že se projekt opět rozjede, tak nemá smysl v tom ale pokračovat.

Seznam podprojektů - tučně jaou značené ty již v tomto vláknu představené:

1) AP 27 (AP27)
2) 321 Prime Search LLR (321)
3) Cullen Prime Search LLR (CUL)
4) Extended Sierpinski Problem LLR (ESP)
5) Fermat Divisor Search LLR (PPS-DIV)
6) Generalized Cullen/Woodall Prime Search LLR (GCW)
7) Prime Sierpinski Problem LLR (PSP)
8 ) Proth Prime Search LLR (PPS)
9 ) Proth Prime Search Extended LLR (PPSE)
10) Proth Mega Prime Search LLR (MEGA)
11) Seventeen or Bust LLR (SOB)
12) Sierpinski / Riesel Base 5 LLR (SR5)
13) Sophie Germain Prime Search LLR (SGS)
14) The Riesel Problem LLR (TRP)
15) Woodall Prime Search LLR (WOO)

16) 321 Sieve (321-Sieve)
17) Proth Prime Search Sieve (PPS-Sieve)
18) Generalized Fermat Prime Search n=15 (GFN-15)
19) Generalized Fermat Prime Search n=16 (GFN-16)
20) Generalized Fermat Prime Search n=17 Low (GFN-17-Low)
21) Generalized Fermat Prime Search n=17 Mega (GFN-17-Mega)
22) Generalized Fermat Prime Search n=18 (GFN-18)
23) Generalized Fermat Prime Search n=19 (GFN-19)
24) Generalized Fermat Prime Search n=20 (GFN-20)
25) Generalized Fermat Prime Search n=21 (GFN-21)
26) Generalized Fermat Prime Search n=22 (GFN-22)
27) Do You Feel Lucky? (GFN World Record)

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 2619
Registrován: pát 03 lis, 2006 10:46

Re: článek o prvočíslech - Prime Grid

#2 Příspěvek od Honza » pát 10 led, 2020 12:50

Pokud by to bylo trošku o PG, tak za těch 15 let od začátku projektu, kterého se účastním, bych mohl něco doplnit.
Bude-li to více o prvočíslech, tak spíše korektury, věcné i jazykové/stylistické.

Článek o PG by se hodil, jedná o extrémně a dlouhodobě stabilní projekt, kde je v neobyčejně míře jasné, co a jakou aplikací počítá, jaké jsou výsledky, kdo za ním stojí a vůbec velká transparentnost.

Prvočísli se nezabýví pouze PG, ještě starší a asi obecně známější je Mersenne a jsou i další.

Tedy spíše doplnění, faktické korekce a podobně, ne psaní.

Uživatelský avatar
RoKro
42.1052631579 %
42.1052631579 %
Příspěvky: 788
Registrován: pon 31 srp, 2009 08:57
rok narození: 29 črc 1970
ID CNT statistics: 10234
Bydliště: Beroun
Kontaktovat uživatele:

Re: článek o prvočíslech - Prime Grid

#3 Příspěvek od RoKro » pát 10 led, 2020 13:02

Mohu nabídnout taky maximálně nějaký proof reading a jazykovou korekturu, ale fakticky o tom nevím nic.

Určitě by se hodilo, aby se v článku člověk dozvěděl něco o praktickém využití výsledků. U biologických projektů je to většinou zřejmé, ale už hůř je pochopitelné proč hledat další prvočíslo.
Jasně, že matika sama je něco jako prvotní výzkum a ten přináší efekt až jeho další aplikací v dalších oborech, ale právě o té aplikaci prvočísel v jiných oborech by bylo fajn vědět.
A určitě dík, že do toho s dcerou jdete!
Obrázek

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: článek o prvočíslech - Prime Grid

#4 Příspěvek od forest » pát 10 led, 2020 22:08

Díky za nabídky pomoci, které rádi využijeme 33iii
Budu moc rád, když se přihlásí ještě další korektoři, případně i nějaký pomocník na tvorbu článku. Čím více nás na tom bude spolupracovat, tím lépe pro finální dílo.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: článek o prvočíslech - Prime Grid

#5 Příspěvek od forest » čtv 13 úno, 2020 21:56

Koukal jsem po našem fóru a zjistil jsem, že u některých podprojektů PG nemáme založena samostatná fóra. Hlavním nedostatkem ale je, že v základních informacích o podprojektech není většinou vysvětleno, čím se vlastně tento podprojekt zabývá, nebo základní vysvětlení té metody.

Rozhodl jsem se tedy, že se pokusím je postupně probrat, zde po jednom představit a pokud v tom bude cokoliv špatně, tak to za vaší pomoci doladit. Rád bych, aby ve finále na webu článek o projektu vypadal obdobně jako u WCG. Tedy všeobecný článek, jehož součástí budou odkazy na jednotlivé podprojekty (aktivní/ukončené) a ty pod nimi budou v samostatných článcích popsány.

Jelikož je aktuálních podprojektů PG 27, tak bych více než kdy jindy uvítal pomoc zasvěcených. Je dost možné, že jich spousta je někde na fóru popsáva, ale není to na místě, kde by to prioritně každý čekal. Na webu v sekci s projekty jsou zase většinou popisy takové, že amatér vlastně nepochopí, co a jak se počítá. Ideální by byly nějaké příklady a to příklady na pokud možno co nejmenších číslech. Příklad s čísly v milionových řádech jen tak nějaký amatér nepochopí. Snažím se článek udělat jako vždy pro BFU. Tedy jasný a srozumitelný i pro čtenáře se základním vzděláním.
Kdokoliv sem kdykoliv může přidat příspěvek s popisem konkrétního podprojektu a nějakým tím příkladem. Tím hodně pomůže ke vzniku tohoto obsáhlého článku.

Do prvního příspěvku v tomto vláknu jsem umístil seznam všech aktuálních podprojektů PG a ty které již budou představeny, budu postupně označovat tučně. Zbytek tedy stále čeká na zpracování. Je dost možné, že některé podprojekty vycházejí ze stejné teorie, nebo se počítají shodnou metodou. Před popisem tedy prosím pište čísla všech podprojektů, kterých se daný popis týká, aby v tom bylo jasno.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: článek o prvočíslech - Prime Grid

#6 Příspěvek od forest » sob 15 úno, 2020 09:29

1) AP 27 Search
Projekt hledá prvočísla, která od sebe dělí shodný počet přirozených čísel, tedy například prvočísla 3,7,11, která od sebe dělí shodně 3 čísla. Na projektu nejde o nalezení největších prvočísel, ale o nalezení největšího množství prvočísel, která jsou od sebe v číselné řadě stejně vzdálená. Počet prvočísel v takové posloupnosti se označuje jako malé k tedy celá zkratka tohoto druhu výzkumu je AP-k.

Základem je Greenova–Taova věta z roku 2004, která je rozšířením Szemerédiho věty z roku 1936 a je speciálním případem Erdősovy-Turánovy hypotézy. Tato teorie ve zkratce říká, že posloupnost prvočísel obsahuje libovolně dlouhé aritmetické posloupnosti. Tedy že pro libovolné přirozené číslo k lze nalézt k-prvkovou aritmetickou posloupnost prvočísel. Jednoduše řečeno, pokud bychom znali všechna prvočísla, tak mezi nimi nalezneme taková, která odděluje v neomezeném sledu stejný počet přirozených čísel.

Nejnižší taková posloupnost (tedy posloupnost tří prvočísel = AP-3) 3, 7, 11, je dána vzorečkem an=3+4n. Tedy a0=3+4*0 (výsledek 3 je prvočíslem), a1=3+4*1 (výsledek 7 je prvočíslem), a2=3+4*2 (výsledek 11 je prvočíslem), a3=3+4*3 (výsledek 15 již není prvočíslem, tedy výpočet končí). Shodný rozestup těchto prvočísel je počet 4 a celkem po sobě v tomto rozestupu následují tři prvočísla. Tedy k=3 => značí se jako AP-3.

Ověřování této teorie nebylo zpočátku velmi výpočetně náročné a šlo se tedy postupně po jednom vzhůru (např. AP-5 = 5, 11, 17, 23, 29 - vzoreček an=5 + 6n - společný rozestup prvočísel je počet 6, tedy AP-5)Ovšem pro čím větší k se posloupnost prvočísel hledá, tím je hledání výpočetně náročnější, o čemž svědčí i historie samotného výzkumu v této oblasti:
- První AP-24 nalezl Jarosław Wróblewski v lednu 2007. Pro jeho nalezení použil 75 počítačů: 15ks 64bitových Athlonů, 15ks dvoujádrových 64bitových procesorů Pentium D 805, 30ks 32bitových Athlonů 2500 a 15ks Duronů 900.
- AP-25 nalezl v květnu 2008 opět Jarosław Wróblewski. Pro jeho nalezení zpracoval prostřednictvím CPU téměř 10.000.000 pracovních jednotek (WU, wokrunit).
- AP-26 bylo nalezeno v dubnu 2010, tentokrát již na projektu PrimeGrid, a to na herní konzoli PlayStation 3. Celkem bylo pro tento výzkum na projektu zpracováno 131.436.182 pracovních jednotek (WU) a to nejen na CPU a PS3, ale už byly zapojeny i grafické karty.
- AP-27 se našlo až o mnoho let později v září 2019, opět na PrimeGridu.

Zdrojem informací byl tento článek, ve kterém naleznete i seznam minimálních a maximálních prozatím nalezených AP-k a jejich výpočty: https://en.wikipedia.org/wiki/Primes_in ... rogression
Zde naleznete databázi celočíselných posloupností, nejen pro prvočísla: http://oeis.org/


Pokud je v popisu podprojektu cokoliv chybného/nejasného, prosím o upozornění a rád to opravím. Případně prosím o doplnění uvedených informací, aby popis byl pro čitatele co nejpřesnější, správný a jasný.

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 2619
Registrován: pát 03 lis, 2006 10:46

Re: článek o prvočíslech - Prime Grid

#7 Příspěvek od Honza » sob 15 úno, 2020 17:19

Za mě vcelku dobré, myslím, že čtenář pochopí, o co při tomto hledání jde.

Možná trochu zavádějící mohou být ty jednotky, tak zkusím narychlo...
U LLR je zrejmé, že se jedná o jeden konkrétní test, který testuje jednoho kandidáta (a v připadě nalezení možná ještě druhého, tj. +1 a -1).
Ale u AP27 se testuje najednou 100 K a shift=10. AP26 testovalo 9 K a shift=1, což je 111 menší jednotka, než AP27.

Takže pokud tomu správně rozumím, tak AP26 mělo 10M jednotek, AP27 mnělo 134M jednotek, ale 111x větších, takže 14 589M jednotek, tedy 14 000x více práce (?!)
Naposledy upravil(a) Honza dne pon 17 úno, 2020 12:36, celkem upraveno 1 x.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: článek o prvočíslech - Prime Grid

#8 Příspěvek od forest » ned 16 úno, 2020 12:46

2) 321 Prime Search LLR (321)
Ptojekt hledá prvočísla pouze v oblasti čísel, pro které platí následující dva vzorečky 3 * 2^n + 1 (Thabit primes of the second kind) a zároveň 3 * 2^n - 1(321 primes of the second kind). Aby číslo n odpovídalo vhodnému výsledku projektu, musí být výsledek v obou výpočtech prvočíslo. Tedy ve společném zápisu platí 3 * 2^n ± 1 je prvočíslem.
Nejmenším číslem n, které tomuto zadání odpovídá je 2 (tedy 3 * 2^2 + 1=13 - je prvočíslem a 3 * 2^2 -1=11 - je prvočíslem). Další čísla byla postupně nalezena 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 98303, 196607, 393215, 786431, 1572863, ...

Základem tohoto výzkumu jsou Thabitova čísla. Thabit byl arabský astronom, matematik a lékař, který žil v letech 836-901. Více o něm zde. Do oboru matematiky se zapsal studiem dokonalých čísel (číslo které se rovná součtu všech svých dělitelů) a hlavně čísel spřátelených (součet všech kladných dělitelů jednoho čísla se rovná druhému číslu a naopak).
V té době byla známa pouze dvě spřátelená čísla a to 220 a 284. Thabit vyslovil následující teorii:
Jsou-li a, b, c prvočísla a pro vhodné n>1 platí a= 3 x 2^n - 1, b=3 x 2^n-1 - 1, c=9 x 2^n-1 -1, pak jsou čísla "2^n x a x b" a "2^n x c" spřátelená.
Ovšem za jeho života se mu nepodařilo ji potvrdit skutečným nalezením další dvojce spřátelených čísel. To se díky Thabitově teorii podařilo jinému arabskému matematikoi Ibn Al-Bannovi ve třináctém století, který našel tato dvě čísla 17296 a 1841 (dle Thabita n=4). Až v roce 1638 nalezl třetí dvojci spřátelených čísel Descartes a to čísla 363.584 a 9.437.056 (dle Thabita n=7).
Thabitova formule neplatí pro všechny spřátelené dvojice. Například pro n<20000 jsou to právě jen výše uvedené dvojice pro n=2,4 a 7.

Jak jsem již uvedl v úvodu, projekt 321 Prime Search LLR hledá prvočísla v číslech dle zadání 3 * 2^n ± 1. Výsledky pomáhají tedy ve všeobecné teorii čísel, hledání spřátelených čísel a zároveň při hledání co největších známých prvočísel. Projekt byl pod křídli PrimeGrid spuštěn v roce 2008.

16) 321 Sieve (321-Sieve)
Projekt se zabývá předběžným filtrováním vhodných a nevhodných kandidátů pro podrobné zkoumání v projektu 321 Prime Search LLR. Nejdříve se tedy projede číselná řada na několik řádů čísel předem dle obou vzorečků v zadání projektu a z výsledků se odeberou předem nevhodní kandidáti pro další zkoumání. Tedy taková čísla, která dle známých teorií prvočíselného rozkladu být prvočísly nemohou. Výsledkem je seznam čísel pro podrobné zkoumání v projektu 321 Prime Search LLR .

Zdroje informací:
https://docplayer.cz/5616188-Fermat-a-t ... cisla.html
https://cs.qwe.wiki/wiki/List_of_prime_numbers
https://dml.cz/bitstream/handle/10338.d ... 94-1_6.pdf
https://en.wikipedia.org/wiki/Main_Page

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 2619
Registrován: pát 03 lis, 2006 10:46

Re: článek o prvočíslech - Prime Grid

#9 Příspěvek od Honza » pon 17 úno, 2020 13:21

Dobrá teorie a historie kolem.

Ad 2)
Přesnější by bylo napsat, že od roku 2008 pro 321 LLR přešel kompletně pod PG.
Takto to vypadá, že to na PG v roce 2008 začalo.

Ad 16)
Jako čtenář si to nedokáži podle popisu moc dobře představit.
Číselná řada čeho? To skoro vypadá, že se jednou vezmou přímo ty kandidáti jeden po druhém a projíždí se. Ale to dělá LLR.
Ono bych spíše řekl, že sieving vezme rozsah (range) toho n, třeba n<50M.
A pak se jede řada čísel a hledá se, jestli dané "malé" číslo není děliteme toho 3 * 2^n ± 1 kde n<50M.
A to jak velké je to malé číslo je hloubka sievingu. Momentálně jsme někde kolem 50P (P jako peta, 10^15).
Na začátku se eliminuje hodně kandidátů, najde se hodně faktorů (protože menší číslo má větší šanci něco jiného dělát...?).
Čím hlouběji se do sievingu je, tím méně kandidátů se vyřazuje...až je výhodnější přejít na LLR.

Z principu sieving řeší nevhodné kandidáty, tedy kdy, kde se najde dělitel.
A LLR z principu ověřuje již jednotlivé kandidáty, jestli jsou prvočíslem či nikolik (případně PRP, probable prime a na něj ověřovací test, ale do takového detailu bych asi již nešel).

Co mě tam zásadně chybí je souvislosit mezi sievingem a LLR, proč se dělá jedno a jak to navazuje na druhé.
Přijde mi to důležité i z toho důvodu, že se to u dalších LLR bude opakovat, ostatně i u Genefer je princip sieving vs test prvočísel.

Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17968
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Re: článek o prvočíslech - Prime Grid

#10 Příspěvek od forest » pon 17 úno, 2020 13:49

Díky za zpětnou vazbu, pokusím se to doplnit. Jsem rád, ža semotné zaměření projektů a jejich pozadí se mně daří dohledat a pochopit, abych to dokázal smysluplně jednoduše popsat. A hlavně, že je ten popis správný. Alespoň u těch dvou zatím zpracovaných.
Pokud si někdo najde čas, budu moc rád za pomoc v podobě obdobně zpracovaného některého ze zbylých podprojektů.

U toho Sievingu jsem se záměrně nepoštěl do velkých podrobností právě z toho důvodu, že se jedná o stejný proces, jen s jiným zadáním parametrů prosévání. Chtěl jsem to rozvést více v tom všeobecném článku, kde budu popisovat i podrobněji jak probíhá LLR. Určitě jsem to tam ale měl napsat.

K Sievingu jsem ale zatím moc zdrojů nenašel a ty co jsem našel, byly hodně odborné. Pokud víš o nějakém dobrém zdroji informací z této oblasti, tak mně prosím napiš odkaz.

Honza
63.1578947368 %
63.1578947368 %
Příspěvky: 2619
Registrován: pát 03 lis, 2006 10:46

Re: článek o prvočíslech - Prime Grid

#11 Příspěvek od Honza » pon 17 úno, 2020 17:14

forest píše:
pon 17 úno, 2020 13:49
K Sievingu jsem ale zatím moc zdrojů nenašel a ty co jsem našel, byly hodně odborné. Pokud víš o nějakém dobrém zdroji informací z této oblasti, tak mně prosím napiš odkaz.
To bohužel nemám, píšu z toho, co jsem se naučil a co mám v hlavě...

Odpovědět

Zpět na „Web, fórum a Galerie CNT“