PrimeGrid
Тип |
Розподілені обчислення Добровольчі обчислення і BOINC Project[d] |
---|---|
Автор(и) | Rytis Slatkevičius |
Перший випуск | 12 червня, 2005 |
Апаратна платформа | Intel x86, x86_64 CPU, AMD x86_64 CPU, Nvidia OpenCL/CUDA, ATI OpenCL |
Платформа | BOINC, PRPNet, Genefer, LLR, PFGW |
Операційна система | Microsoft Windows, Linux, Mac OS 10.5+ |
primegrid.com | |
PrimeGrid у Вікісховищі? |
PrimeGrid — проект добровільних розподілених обчислень на платформі BOINC і PRPNet, метою якого є пошук простих чисел різного виду. Проект стартував 12 червня 2005 року.
Основна мета проекту — нести задоволення пересічному користувачу від знаходження простих чисел. Другою метою PrimeGrid є надання відповідних навчальних матеріалів про прості числа.
І нарешті, прості числа грають центральну роль в криптографічних систем, які використовуються для комп'ютерної безпеки. Через вивчення простих чисел можна показати, скільки вимагається обчислень, щоб зламати код шифрування і таким чином визначити, чи є поточні схеми безпеки достатньо безпечними.
Участь у проекті PrimeGrid можлива у два способи: через BOINC і через Project Staging Area (PSA)
Зміст
- 1 Історія проекту
- 2 Визначні дати
- 3 Підпроекти (BOINC)
- 4 Початкові підпроекти
- 5 Підпроекти AP
- 6 Підпроекти LLR
- 6.1 321 Prime Search
- 6.2 Cullen Prime Search
- 6.3 Extended Sierpinski Problem
- 6.4 Fermat Divisor Search
- 6.5 Generalized Cullen/Woodall Prime Search
- 6.6 Prime Sierpinski Problem
- 6.7 Proth Prime Search
- 6.8 Seventeen or Bust
- 6.9 Sierpinski/Riesel Base 5 Problem
- 6.10 Sophie Germain Prime Search
- 6.11 The Riesel Problem
- 6.12 Twin Prime Search
- 6.13 Woodall Prime Search
- 7 Підпроекти PRP
- 8 Підпроекти Sieve
- 9 Project Staging Area (PSA)
- 10 Бейджики
- 11 Див. також
- 12 Примітки
- 13 Джерела
Історія проекту[ред. | ред. код]
2005 рік[ред. | ред. код]
Проект започатковано 12 червня 2005 року приблизно о 14:00 UTC. Message@Home (тепер PrimeGrid) відкрив реєстрацію для 50 перших користувачів. Проект стартував на домашньому лептопі Rytis Slatkevičius.
Message@Home було розроблено як тестовий проект для PerlBOINC у спробі реалізувати BOINC сервер мовою програграмування . Першочерговою метою проекту на PerlBOINC було отримати короткі завдання (WU) із стандартних постійним результатом. Першим проектом був Message7, в якому ми намагалися за допомогою прямого перебору відновити повідомлення, зашифроване за допомогою md5. У серпні 2005 до проекту було долучено застосунок RSA 640 Factoring Challenge. Подібно до Message7 у цьому проекті ми намагалися прямим перебором віднайти дільник для 640 цифрового RSA ключа. Message7 було припинено. 1 вересня 2005 року після невеличкої наради було обрано нову назву для проекту, PrimeGrid було обрано з варіації PrimeGrid@Home, що була запропонована користувачем на ім'я Heffed. За це він отримав 999 очок. :)
У листопаді 2005 зусиллями іншого проекту було факторизовано RSA 640, отже PrimeGrid рушив на штурм RSA 768. Оскільки шанси на факторизацію залишалися нескінченно малими, подальший розвиток залишено для PerlBOINC.
2006 рік[ред. | ред. код]
У березні 2006 проект RSA 768 було перервано для запуску нового, PrimeGen. У цьому проекті ми намагалися побудувати базу послідовних простих чисел, що на деякий час навернуло PrimeGrid на стежину пошуку простих чисел. Вторинною метою залишалась допомога RSA Factoring Challenges. Однак, незабаром з'ясувалося, що ці зусилля теж мають нескінченно малі шанси на успіх. Тим не менш пошук проекту, гідного розподілених обчислень, було продовжено.
В червні 2006 розпочався діалог з ведучими проекту Riesel Sieve із пропозицією перенести їхній проект на рейки BOINC. Rytis надавав підтримку PerlBOINC і команда Riesel Sieve успішно започаткувала їхній відсів (sieve), так само як застосунок LLR для пошуку простих чисел. У співпраці з Riesel Sieve PrimeGrid вдалось реалізувати застосунок LLR в партнерстві з іншими проектом з пошуку простих чисел, Twin Prime Search. У листопаді 2006, підпроект TPS LLR було офіційно запущено в PrimeGrid.
2007 рік[ред. | ред. код]
Менш ніж за два місяці, у січні 2007 рекордну пару простих чисел-близнюків було знайдено в початковому ручному проекті. PrimeGrid та TPS продовжили пошук ще більших пар простих-близнюків.
Літо 2007 виявилось досить спекотним, адже саме тоді було запущено пошук простих Cullen та Woodall. Восени, завдяки партнерським відносинам з Prime Sierpinski Problem і проектом 321, ще більше пошуків простих було додано. Додатково було додано 2 відсіва: Prime Sierpinski Problem об'єднаний відсів, що включає підтримку відсіву за проблемою Seventeen or Bust; а також комбінований Cullen/Woodall відсів:
- у липні 2007 року розпочато підпроект Woodall LLR.
- у серпні 2007 року розпочато підпроект Cullen LLR.
- 15 вересня 2007 року розпочато об'єднаний Cullen/Woodall Sieve.
- 13 жовтня 2007 року розпочато підпроект PSP Sieve.
- 18 листопада 2007 року розпочато підпроект 321 LLR.
- 11 грудня 2007 року розпочато підпроект PSP LLR.
Восени 2007 PrimeGrid мігрував деякі системи з PerlBOINC до стандартного програмного забезпечення BOINC. Тим не менш, багато з сервісів до цього часу залишаються на базі PerlBOINC.
2008 рік[ред. | ред. код]
- 29 лютого 2008 року встановлено співпрацю з Proth Search.
- 15 березня 2008 року розпочато серію челенджів. Встановлено рекорд одного дня — понад 820К очок.
- 13 квітня 2008 року Project Staging Area додано задля допомоги у адаптації нових застосунків для BOINC.
- 10 березня 2008 року завершено підпроект PrimeGen.
- 28 серпня 2008 року чат Meebo додано до форуму.
- 26 грудня 2008 року розпочато підпроект AP26.
2009 рік[ред. | ред. код]
- У лютому 2009 року PrimeGrid товаришує з 12121 Search у пошуку простих форм 121·2n−1 та 27·2n−1. PrimeGrid додає форму +1 і розпочинає пошук усіх чотирьох форм у підпроекті 27121 Search.
- 12 травня 2009 року розпочато Factorial Prime Search.
- 3 серпня 2009 року — в PrimeGrid введено систему бейджів.
- 16 серпня 2009 року — розпочато Sophie Germain Prime Search.
- 16 вересня 2009 року PrimeGrid долучається до підпроектів Seventeen or Bust задля розв'язання проблеми Серпинського.
- 20 жовтня 2009 року випущено ppsieve для PPSE sieve, що у 6 разів швидший за попередній.
- 5 листопада 2009 року розпочато Generalized Fermat Prime Search.
- 8 листопада 2009 року з'явилась надія на появу застосунку для GPU в PrimeGrid. Розпочато розробку та тестування.
- У грудні 2009 року додано підтримку CUDA для AP26.
2010 рік[ред. | ред. код]
- 1 лютого 2010 року офіційно розпочинається співпраця з Seventeen or Bust заради розв'язання проблеми Серпінського.
- 7 березня 2010 року відновлено підпроект The Riesel Problem з TRP (Sieve).
- 9 березня 2010 року розпочато тестування CUDA в Proth Prime Sieve.
- 19 березня 2010 року розпочато підпроект extended Sierpinski problem.
- 21 березня 2010 року розпочато підпроект The Riesel Problem (LLR).
2011 рік[ред. | ред. код]
- На початку січня 2011 року розпочалась співпраця PrimeGrid з Sierpinski/Riesel Base 5 Project. Підпроект SR5 було розпочато в PRPNet у тестовому режимі.
- 22 квітня 2011 року призупинено підпроект 321 Prime Search (Sieve).
- 1 жовтня 2011 року в PRPNet розпочато підпроект The dual Sierpinski problem (Five or Bust).
2012 рік[ред. | ред. код]
На початку січня 2012 програма GeneferCUDA була портована з клієнта PRPNet до BOINC. Почавши у статусі тестового, дуже швидко Genefer набув статусу офіційного підпроекту. Протягом лише першого місяця у проекті було віднайдено 2 нових простих числа форми General Fermat Number (GFN).
2013 рік[ред. | ред. код]
- Наприкінці січня 2013 року відбулась міграція проекту PrimeGrid на новий сервер.
- У лютому 2013 року усі LLR додатки отримали підтримку AVX для 64-бітних платформ.
- У травні 2013 року введено нову систему бейджиків.
- 28 травня 2013 року підпроект PPS-Sieve отримав підтримку OpenCL для Mac/ATI.
- Наприкінці червня 2013 року введено систему бонусного преміювання за участь у проектах із перевірки гіпотез SR5, TRP, PSP і SoB (+10 %) та підпроектів з довготривалими завданнями: 321, TRP-LLR (+10 %), CUL, WOO (+20 %), PSP (+35 %), SoB, GFN-WR (+50 %).
- У вересні 2013 року додатки GFN отримали підтримку AVX та OpenCL.
2014 рік[ред. | ред. код]
- У травні 2014 року розпочато повторну перевірку в BOINC результатів підпроекту SR5, отриманих в PRPNet.
- На початку червня 2014 року підпроект Extended Sierpinski Problem портовано з PRPNet до BOINC.
- 29 червня 2014 року розпочато підпроект ESP Sieve — підпроект «сіялка» для підпроекта ESP LLR.
- 18 липня 2014 року підпроект PPS-MEGA портовано з PRPNet до BOINC.
2015 рік[ред. | ред. код]
- У жовтні 2015 року підпроекти GFN 32768, GFN 65536, GFN 131072 (Low) і GFN 131072 (Mega) портовано з PRPNet до BOINC, а у листопаді — GFN 262144, GFN 524288 та GFN 1048576.
2016 рік[ред. | ред. код]
- У вересні 2016 року розпочато підпроект AP27.
- У жовтні 2016 року розпочато підпроект GCW (Sieve).
2017 рік[ред. | ред. код]
- У квітні 2017 року розпочато підпроект GCW (LLR).
- 25 квітня 2017 року завершено підпроект TRP (Sieve).
- У квітні 2017 року в PRPNet призупинено підпроекти Wall-Sun-Sun і Wieferich.
2018 рік[ред. | ред. код]
- Наприкінці січня 2018 року зупинено видачу завдань GFN-15 для CPU. Підпроект став виключно GPU-сумісний.
2019 рік[ред. | ред. код]
- У лютому 2019 року розпочато підпроект Do You Feel Lucky?.
- 1 травня 2019 року завершено підпроект GCW (Sieve).
- У травні 2019 року усі LLR додатки отримали підтримку AVX-512.
- 6 вересня 2019 року розпочато підпроект Fermat Divisor Search.
Визначні дати[ред. | ред. код]
- 12.06.2005 — народився Message@Home з підпроектом Message7, у якому було відкрито реєстрацію для перших 50 користувачів
- 01.09.2005 — Message@Home змінює назву на PrimeGrid
- 07.08.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 2013992·22013992−1
- 20.08.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 2367906·22367906−1
- 21.12.2007 — в PrimeGrid знайдено найбільше відоме просте Вудала: 3752948·23752948−1
- 20.04.2009 — в PrimeGrid знайдено найбільше відоме просте Каллена: 6328548·26328548+1
- 25.07.2009 — в PrimeGrid знайдено найбільше відоме просте Каллена: 6679881·26679881+1
- 07.12.2009 — в PRPNet знайдено найбільше відоме узагальнене просте Вудала: 563528·13563528−1
- 12.04.2010 — в PrimeGrid знайдено першу відому арифметичну прогресію 26 простих чисел: 43142746595714191+23681770*23#*n для n=0..25
- 04.10.2010 — в PRPNet знайдено найбільше відоме факторіальне просте: 94550!−1
- 14.12.2010 — в PRPNet знайдено найбільше відоме факторіальне просте: 103040!−1
- 20.12.2010 — в PRPNet знайдено найбільше відоме прайморіальне просте: 843301#−1
- 08.02.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 145310262144+1
- 24.02.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Вудала: 404882·43404882−1
- 11.06.2011 — в PRPNet знайдено найбільше відоме факторіальне просте: 110059!+1
- 22.06.2011 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 9·22543551+1 ділить F(2543548)
- 29.10.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 361658262144+1
- 19.11.2011 — в PRPNet знайдено найбільше відоме узагальнене просте Ферма: 75898524288+1
- 25.12.2011 — в PrimeGrid знайдено найбільшу відому пару простих−близнюків: 3756801695685·2666669±1
- 29.01.2012 — в PRPNet знайдено найбільше відоме узагальнене просте Каллена: 427194·113427194+1
- 28.02.2012 — в PRPNet знайдено найбільше відоме прайморіальне просте: 1098133#−1
- 09.04.2012 — в PrimeGrid знайдено найбільше відоме просте Софі Жермен: 18543637900515·2666667−1, 18543637900515·2666668−1 (2p+1)
- 15.06.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 341112524288+1
- 20.06.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 356926524288+1
- 08.08.2012 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 475856524288+1
- 13.05.2013 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 57·22747499+1 ділить F(2747497)
- 29.12.2013 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 37292·51487989+1
- 14.01.2014 — в PrimeGrid знайдено найбільше відоме просте 321: 3·210829346+1
- 17.01.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 59912·51500861+1
- 31.01.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 178658·51525224−1
- 06.02.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 22934·51536762−1
- 21.03.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 330286·51584399−1
- 09.04.2014 09:13:42 UTC — в PrimeGrid знайдено найбільше відоме просте за основою 5: 104944·51610735−1
- 09.04.2014 18:33:30 UTC — в PrimeGrid знайдено найбільше відоме просте за основою 5: 207394·51612573−1
- 25.04.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 326834·51634978−1
- 19.06.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 22478·51675150−1
- 27.06.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 138172·51714207−1
- 23.07.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 24032·51768249+1
- 25.07.2014 — в PrimeGrid знайдено найбільший відомий дільник числа Ферма: 193·23329782+1 ділить F(3329780)
- 17.08.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 133778·51785689+1
- 21.09.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 325918·51803339−1
- 18.10.2014 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 109208·51816285+1
- 22.11.2014 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211484018−1
- 13.03.2015 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211731850−1
- 23.05.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 144052·52018290+1
- 23.06.2015 — в PrimeGrid знайдено найбільше відоме просте 321: 3·211895718−1
- 21.10.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 100186·52079747−1
- 10.11.2015 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 154222·52091432+1
- 11.01.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 306398·52112410−1
- 29.02.2016 — в PrimeGrid знайдено найбільше відоме просте Софі Жермен: 2618163402417·21290000−1, 2618163402417·21290001−1 (2p+1)
- 06.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 77072·52139921+1
- 15.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 92158·52145024+1
- 25.03.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 296024·52185270−1
- 30.05.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 53546·52216664−1
- 20.08.2016 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 180062·52249192−1
- 14.09.2016 — в PrimeGrid знайдено найбільшу відому пару простих−близнюків: 2996863034895·21290000±1
- 08.10.2016 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 682156·79682156+1
- 31.10.2016 — в PrimeGrid знайдено найбільше відоме просте Прота, а також найбільше відоме просте Кольбера: 10223·231172165+1
- 21.08.2017 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1341174·531341174+1
- 25.08.2017 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 171362·52400996−1
- 29.08.2017 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 9194441048576+1
- 17.09.2017 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 301562·52408646−1
- 18.01.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1323365·1161323365+1
- 11.03.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 1806676·411806676+1
- 21.03.2018 — в PrimeGrid знайдено найбільше відоме просте Вудала: 17016602·217016602+1
- 19.06.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 327926·52542838−1
- 20.06.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 81556·52539960+1
- 29.07.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 66916·52628609−1
- 15.08.2018 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 194368·52638045−1
- 31.10.2018 — в PrimeGrid знайдено найбільше відоме узагальнене просте Ферма: 10590941048576+1
- 26.04.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 138514·52771922+1
- 21.06.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 88444·52799269−1
- 23.06.2019 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 322498·52800819−1
- 02.09.2019 — в PrimeGrid знайдено найбільше відоме узагальнене просте Каллена: 2805222·252805222+1
- 23.09.2019 — в PrimeGrid знайдено першу відому арифметичну прогресію з 27 простих чисел: 224584605939537911+81292139*23#*n для n=0..26
Підпроекти (BOINC)[ред. | ред. код]
- 321 Prime Search (LLR)
- Cullen Prime Search (LLR)
- Extended Sierpinski Problem (LLR)
- Fermat Divisor Search (LLR)
- Generalized Cullen/Woodall Prime Search (LLR)
- Prime Sierpinski Problem (LLR)
- Proth Prime Search (LLR)
- Proth Prime Search Extended (LLR)
- Proth Mega Prime Search (LLR)
- Seventeen or Bust (LLR)
- Sierpinski/Riesel Base 5 Problem (LLR)
- Sophie Germain Prime Search (LLR)
- The Riesel Problem (LLR)
- Woodall Prime Search (LLR)
- 321 Prime Search Sieve
- Proth Prime Search (Sieve)
- Generalized Fermat Prime Search (n=15)
- Generalized Fermat Prime Search (n=16)
- Generalized Fermat Prime Search (n=17 low)
- Generalized Fermat Prime Search (n=17 mega)
- Generalized Fermat Prime Search (n=18)
- Generalized Fermat Prime Search (n=19)
- Generalized Fermat Prime Search (n=20)
- Generalized Fermat Prime Search (n=21)
- Generalized Fermat Prime Search (n=22)
- Do You Feel Lucky?
- AP27 Search
Завершені / призупинені підпроекти[ред. | ред. код]
- Message7
- PrimeGen
- RSA 640
- RSA 768
- Twin Prime Search
- AP26
- Cullen/Woodall Sieve
- Sierpinski (ESP/PSP/SoB) Sieve
- The Riesel Problem (Sieve)
- Generalized Cullen/Woodall Sieve
Застосунки[ред. | ред. код]
Переваги застосунків[ред. | ред. код]
- виконання завдань Sieve на GPU дає перевагу над CPU у 10-100 разів (в залежності від моделі GPU і CPU)
- виконання завдань Sieve на GPU з CUDA (NVIDIA) має перевагу над аналогічним за рівнем GPU з OpenCL (AMD)
- виконання завдань Genefer / Genefer (World Record) на GPU (NVIDIA) з використанням CUDA має перевагу над OpenCL для відеокарт родини Fermi та старших
- виконання завдань Genefer / Genefer (World Record) на GPU (NVIDIA) з використанням OpenCL має перевагу над CUDA для відеокарт родини Kepler та молодших
- виконання завдань LLR та Genefer з оптимізацією під інструкції AVX сучасних Intel процесорів (Sandy/Ivy Bridge, Haswell) дає перевагу над SSE3 у декілька разів
- виконання завдань Sieve на 64-бітному CPU дає перевагу над 32-бітних CPU клієнтом у ~1.7 раза
- виконання завдань LLR на 64-бітному CPU має перевагу над 32-бітним CPU
Початкові підпроекти[ред. | ред. код]
Message7[ред. | ред. код]
Першим проектом Message@Home (тепер PrimeGrid) був Message7, в якому за допомогою прямого перебору намагалися відновити повідомлення, зашифроване за допомогою md5. У серпні 2005 року Message7 було припинено.
RSA 640[ред. | ред. код]
У серпні 2005 до проекту було долучено застосунок RSA 640 Factoring Challenge. Подібно до Message7 у цьому проекті відбувались намагання прямим перебором віднайти дільник для 640 цифрового RSA ключа.
У листопаді 2005 зусилями іншого проекту було факторизовано RSA 640, отже PrimeGrid рушив на штурм RSA 768 Factoring Challenge.
RSA 768[ред. | ред. код]
Оскільки шанси на факторизацію RSA 768 виявились нескінченно малими, подальший розвиток залишено для PerlBOINC. У березні 2006 проект RSA 768 було перервано для запуску нового, PrimeGen.
PrimeGen[ред. | ред. код]
У березні 2006 було запущено проект PrimeGen, метою якого було побудувати базу послідовних простих чисел. Однак, незабаром з'ясувалося, що ці зусилля мають нескінченно малі шанси на успіх, отже підпроект було зупинено.
Підпроекти AP[ред. | ред. код]
AP26[ред. | ред. код]
Арифметична прогресія — послідовність чисел, різниця між послідовними членами якої є сталим числом. Наприклад послідовність 3, 5, 7, 9, 11, 13, 15, … є арифметичною прогресією з фіксованою різнецею, що дорівнює 2.
Таким чином, арифметична прогресія простих чисел — це послідовність простих чисел, різниця між послідовними членами якої є сталим числом. Наприклад, послідовність 3, 7, 11 є арифметичною прогресією 3 простих із фіксованою різницею 4.
Для арифметичної прогресії (AP) простих, AP-k означає k простих форми p+d*n для деяких p і d, а n приймає значення від 0 до k−1. Арифметичну прогресію, що наведено вище, можна записати як AP-3 виду 3+4·n для n=0,1,2.
n=0; 3+4·0 = 3+0 = 3
n=1; 3+4·1 = 3+4 = 7
n=2; 3+4·2 = 3+8 = 11
Іншим прикладом арифметичної прогресії простих є AP-10 виду 199+210·n для n=0..9. Вона продукує наступну послідовність простих: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089.
AP-k також інколи записують як PAP-k (Primes in Arithmetic Progression).
Підпроект AP26 займався пошуком найдовшої (але не найбільшої) арифметичної прогресії простих чисел. На той час найдовшою відомою AP була AP-25, що була віднайдена 17 травня 2008 року і має вигляд 6171054912832631+366384·23#·n (8132758706802551)
Результати підпроекту[ред. | ред. код]
12 квітня 2010 року у підпроекті AP26 було знайдено першу відому арифметичну прогресію 26 простих чисел:
AP | Тип | Дата | Автор |
---|---|---|---|
43142746595714191+23681770*23#*n для n=0..25 | AP26 | 12.04.2010 | Benoãt Perichon |
, де 23#=2·3·5·7·11·13·17·19·23=223092870
У травні 2010 року підпроект AP26 було завершено.
AP27 Search[ред. | ред. код]
20 вересня 2016 року підпроект пошуку арифметичної прогресії простих чисел було відновлено під назвою AP27 (арифметична прогресія 27 простих чисел)
Результати підпроекту[ред. | ред. код]
23 вересня 2019 року у підпроекті AP27 було знайдено першу відому арифметичну прогресію 27 простих чисел:
AP | Тип | Дата | Автор |
---|---|---|---|
224584605939537911+81292139*23#*n для n=0..26 | AP27 | 23.09.2019 | Rob Gahan |
, де 23#=2·3·5·7·11·13·17·19·23=223092870
Підпроекти LLR[ред. | ред. код]
321 Prime Search[ред. | ред. код]
Підпроект 321 Prime Search — це продовження проекту 321 Search, що було розпочато Paul Underwood, який шукав прості виду 3·2n−1. PrimeGrid додав пошук за формою +1 і продовжує пошук аж до n=25M.
Експоненти n, для яких відповідні числа форми 3·2n+1 прості, утворюють послідовність:
1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912, 20909, 34350, 42294, 42665, 44685, 48150, 54792, 55182, 59973, 80190, 157169, 213321, 303093, 362765, 382449, 709968, 801978, 916773, 1832496, 2145353, 2291610, 2478785, 5082306, 7033641, 10829346
Експоненти n, для яких відповідні числа форми 3·2n−1 прості, утворюють послідовність:
0, 1, 2, 3, 4, 6, 7, 11, 18, 34, 38, 43, 55, 64, 76, 94, 103, 143, 206, 216, 306, 324, 391, 458, 470, 827, 1274, 3276, 4204, 5134, 7559, 12676, 14898, 18123, 18819, 25690, 26459, 41628, 51387, 71783, 80330, 85687, 88171, 97063, 123630, 155930, 164987, 234760, 414840, 584995, 702038, 727699, 992700, 1201046, 1232255, 2312734, 3136255, 4235414, 6090515, 11484018, 11731850, 11895718
Про 321 Search[ред. | ред. код]
Проект 321 Search було розпочато у лютому 2003 із листа від Paul Underwood, що шукав допомогу зацікавлених у пошуку простих виду 3·2n−1. Початкова мета була перевірити результати роботи вже проведені проектом Proth Search і розширити перелік простих до експоненти в 1 мільйон (n=1M). Ця мета була швидко досягнута, тому вони розвинули мету з пошуку мега великих простих, для яких вони провели відсів аж до n=5M.
Результати підпроекту[ред. | ред. код]
Прості числа виду 3·2n±1, що було знайдено у PrimeGrid (станом на 23 червня 2015 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
3·24235414−1 | 1 274 988 | 23.03.2008 | Dylan Bennett |
3·22291610+1 | 689 844 | 11.08.2008 | Thomas Wolfram |
3·25082306+1 | 1 529 928 | 03.04.2009 | Andy Brady |
3·26090515−1 | 1 833 429 | 24.04.2010 | David Mumper |
3·27033641+1 | 2 117 338 | 21.02.2011 | Michael Herder |
3·210829346+1 | 3 259 959 | 14.01.2014 | Sai Yik Tang |
3·211484018−1 | 3 457 035 | 22.11.2014 | Serhiy Gushchak |
3·211731850−1 | 3 531 640 | 13.03.2015 | Karsten Klopffleisch |
3·211895718−1 | 3 580 969 | 23.06.2015 | Michael Schulz |
Cullen Prime Search[ред. | ред. код]
Cullen Prime Search — це підпроект з пошуку простих чисел Каллена. В теорії чисел число Каллена — натуральне число виду Cn = n·2n+1
Експоненти n, для яких відповідні числа Каллена прості, утворюють послідовність:
1, 141, 4713, 5795, 6611, 18496, 32292, 32469, 59656, 90825, 262419, 361275, 481899, 1354828, 6328548, 6679881
В 1976 році Христофер Хулей (англ. Christopher Hooley) показав, що майже всі числа Каллена складені. Доведення Христофера Хулей було перероблено математиком Хірмі Суяма, щоб показати, що воно вірне для будь-якої послідовності n·2n+a+b, де a і b — цілі числа, а також частково для чисел Вудала.
Існує гіпотеза, що простих чисел Каллена нескінчено багато.
Результати підпроекту[ред. | ред. код]
Прості числа Каллена, що було знайдено у PrimeGrid (станом на 25 липня 2009 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
6328548·26328548+1 | 1 905 090 | 20.04.2009 | Dennis R. Gesker |
6679881·26679881+1 | 2 010 852 | 25.07.2009 | Anonymous |
Extended Sierpinski Problem[ред. | ред. код]
В 1962 році Джон Селфридж[en] висунув гіпотезу, що число Серпінського k = 78557 є найменшим з таких чисел. Проблема Серпінського намагається підтвердити цю гіпотезу. В 1976 році Натан Мендельсон (Nathan Mendelsohn) висунув гіпотезу, що другим числом Серпінського є просте число k = 271129. Prime Sierpinski Problem намагається підтвердити гіпотезу, що це число є найменшим простим числом Серпінського.
Якщо обидві ці проблеми будуть розв'язані і буде встановлено, що k = 78557 є найменшим числом Серпінського, і k = 271129 — найменшим простим числом Серпінського, однак це не доводить, що k = 271129 є другим числом Серпінського. Оскільки Prime Sierpinski Problem перевіряє всі прості k у проміжку 78557 < k < 271129, все що достатньо зробити, це перевірити всі складені з проміжку 78557 < k < 271129. Таким чином було розпочато проект Extended Sierpinski Problem.
Станом на квітень 2018 року пошук залишається для 10-ти k, до яких досі не знайдено простих:
91549, 99739, 131179, 163187, 200749, 202705, 209611, 227723, 229673, 238411
Результати підпроекту[ред. | ред. код]
Прості, що було знайдено у PrimeGrid (станом на 3 квітня 2018 року):
Прості підпроекту ESP | |||
---|---|---|---|
Просте число | Цифр | Дата | Автор |
227753·291397+1 | 27 519 | 13.03.2010 | Lennart Vogel |
261203·2354561+1 | 106 739 | 20.03.2010 | Lennart Vogel |
185449·2435402+1 | 131 075 | 21.03.2010 | Rodger Ewing |
167957·2417463+1 | 125 675 | 21.03.2010 | Brian Carpenter |
208381·2463068+1 | 139 403 | 22.03.2010 | Lennart Vogel |
168587·2545971+1 | 164 359 | 23.03.2010 | Steve Martin |
187681·2573816+1 | 172 742 | 23.03.2010 | Lennart Vogel |
225679·2620678+1 | 186 849 | 24.03.2010 | Lennart Vogel |
85013·2699333+1 | 210 526 | 25.03.2010 | Steve Martin |
107929·21007898+1 | 303 413 | 05.04.2010 | Brian Carpenter |
98749·21045226+1 | 314 650 | 09.04.2010 | Rodger Ewing |
154801·21305084+1 | 392 875 | 29.04.2010 | Rodger Ewing |
219259·21300450+1 | 391 480 | 29.04.2010 | Lennart Vogel |
250463·21316921+1 | 396 439 | 30.04.2010 | Rodger Ewing |
147559·22562218+1 | 771 310 | 27.03.2012 | Rodger Ewing |
198677·22950515+1 | 888 199 | 23.10.2012 | Ardo van Rangelrooij |
94373·23206717+1 | 965 323 | 10.03.2013 | Jörg Meili |
211195·23224974+1 | 970 820 | 11.03.2013 | Ardo van Rangelrooij |
161041·27107964+1 | 2 139 716 | 06.01.2015 | Martin Vanc |
193997·211452891+1 | 3 447 670 | 03.04.2018 | Tom Greer |
Fermat Divisor Search[ред. | ред. код]
Підпроект з пошуку простих чисел Прота k·2n+1 — дільників чисел Ферма.
Роботу розпочато з пошуку простих для k=19683 аж до n=4M.
У другій стадії відбуватиметься пошук для 5<=k<=49 аж до n=9M.
Підпроект вважається частиною проекту Proth Prime Search, отож всі результати і досягнення зараховуються до PPS-LLR.
Generalized Cullen/Woodall Prime Search[ред. | ред. код]
Узагальнене число Каллена визначається як число виду n·bn+1, де n+2>b. Якщо просте число можна записати таким чином, його називають узагальненим простим числом Каллена.
Узагальнене число Вудала визначається як число виду n·bn−1, де n+2>b. Якщо просте число можна записати таким чином, його називають узагальненим простим числом Вудала.
Метою GCW Prime Search є пошук узагальнених простих Каллена і Вудала за основами, для яких досі не віднайшли жодного простого. З самого початку GCW13 Search пощастило знайти найбільше відоме узагальнене просте Вудала: 563528·13563528−1.
Наступні бази було обрано для подальшого пошуку узагальнених простих:
- Вудал: b = 43, 104 і 121
- Каллен: b = 13, 25, 29, 41, 47, 49, 53, 55, 68, 69, 73, 79, 101, 109, 113, 116 і 121
Основа 149 — наступна основа без відомих простих для обох і GC, і GW.
Початкова глибина відсіву для цих основ становила 1.5T. Lennart Vogel перевірив на простоту всі основи аж до n=100K (лише GW121 до 50K). Як побачимо нижче, це все була подвійна перевірка попередніх зусиль.
Результати проекту[ред. | ред. код]
b | Узагальнене | Просте число | Цифр | Дата | Автор |
---|---|---|---|---|---|
13 | Woodall | 563528·13563528−1 | 627 745 | 07.12.2009 | Lennart Vogel |
43 | Woodall | 404882·43404882−1 | 661 368 | 24.02.2011 | Ricky L. Hubbard |
104 | Woodall | 129840·104129840−1 | 261 897 | 26.05.2010 | Sideshow_Larry |
121 | Woodall | 94112·12194112−1 | 196 021 | 19.05.2010 | unconnected |
13 | Cullen | ||||
25 | Cullen | 2805222·252805222+1 | 3 921 539 | 02.09.2019 | Tom Greer |
29 | Cullen | ||||
41 | Cullen | 1806676·411806676+1 | 2 913 785 | 11.03.2018 | Hiroyuki Okazaki |
47 | Cullen | ||||
49 | Cullen | ||||
53 | Cullen | 1341174·531341174+1 | 2 312 561 | 21.08.2017 | Hiroyuki Okazaki |
55 | Cullen | ||||
68 | Cullen | 129897·68129897+1 | 238 043 | 25.05.2010 | [SG-SPEG]Puzzle-Peter |
69 | Cullen | ||||
73 | Cullen | ||||
79 | Cullen | 682156·79682156+1 | 1 294 484 | 08.10.2016 | Franz-Xaver Harvanek |
101 | Cullen | ||||
109 | Cullen | ||||
113 | Cullen | 427194·113427194+1 | 877 069 | 29.01.2012 | Ricky L. Hubbard |
116 | Cullen | 1323365·1161323365+1 | 2 732 038 | 18.01.2018 | Scott Brown |
121 | Cullen |
Prime Sierpinski Problem[ред. | ред. код]
Числом Серпінського називається таке непарне натуральне число k, що для довільного натурального n число k·2n+1 не є простим.
Послідовність відомих чисел Серпінського починається так:
78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, …
Проблему Серпінського можна сформулювати так: «Яким є найменше число Серпінського?», а проблему простого Серпінського: «Яким є найменше просте число Серпінського?»
Найменше доведене просте число Серпінського — 271129. Щоб довести, що 271129 є найменшим простим числом Серпінського, необхідно показати, що кожне просте k, таке, що 0 < k < 271129, не є числом Серпінського.
Seventeen or Bust працює над проблемою Серпінського, а Prime Sierpinski Project — над проблемою простого Серпінського.
Для наступних k до цього часу залишаються невідомі прості для кожного з проектів:
Seventeen or Bust | Prime Sierpinski Project |
---|---|
21181 | |
22699 | 22699[1] |
24737 | |
55459 | |
67607 | 67607[1] |
79309 | |
79817 | |
152267 | |
156511 | |
222113 | |
225931 | |
237019 |
Результати підпроекту[ред. | ред. код]
Прості, що було знайдено у PrimeGrid (станом на 17 вересня 2017 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
168451·219375200+1 | 5 832 522 | 17.09.2017 | Ben Maloney |
Proth Prime Search[ред. | ред. код]
У підпроекті Proth Prime Search відшукуються прості числа виду k·2n+1, за умови 2n > k, що часто називають простими числами Прота. Цей проект також дає можливість віднайти дільники для «класичних» чисел Ферма, узагальнених чисел Ферма чи розширених узагальнених чисел Ферма. Як тільки у PrimeGrid знаходиться просте Прота, воно одразу проходить додаткову перевірку на сервері PrimeGrid, чи є воно дільником однієї з форм чисел Ферма.
Proth Prime Search проводиться у співпраці з проектом Proth Search. Початковою метою проекту PrimeGrid було перевірити всю попередню роботу проекту Proth Search аж до n=500K для непарних k<1200 і заповнити будь-які можливі прогалини. PrimeGrid перевірив все аж до n=200000 і знайшов деякі прості, що було випущено минулим пошуком. Незважаючи на те, що прості вже надто малі, щоб потрапити до бази Top 5000, цей пошук був важливим, адже він міг призвести до відшукання нових дільників для «класичних» чисел Ферма, узагальнених чисел Ферма або розширених узагальнених чисел Ферма.
Про Proth Search[ред. | ред. код]
Проект Proth Search було започатковано 1998 року за участю Ray Ballinger та Wilfrid Keller, які організували розподілені обчислення для знаходження простих Прота (прості виду k·2n+1) для k < 300. Ray був зацікавлений у пошуку простих, а Wilfrid — у пошуку дільників для чисел Ферма. Пізніше проект розширив межі свого пошуку до k < 1200. Mark Rodenkirch (aka rogue) допомагав Ray в утримані веб-сайту останні декілька літ.
На початку 2008 року PrimeGrid та Proth Search розпочали співпрацю з надання програмного забезпечення для об'єднання зусиль розподілених обчислень.
Від того часу PrimeGrid веде пошук простих Прота у декількох різних підпроектах, як у вигляді підпроектів BOINC, так і в PRPNet.
Станом на 6 вересня 2019 року в PrimeGrid існує 4 діапазони пошуку простих Прота, які оформлені як 4 різних підпроекта BOINC:
- PPS: k·2n+1 для k<1200
- PPSE: k·2n+1 для 1200<k<10000
- MEGA: k·2n+1 для 100<k<300 і 3.322M<=n<3.6M
- DIV: k·2n+1 для 5<=k<=49 і n<=9M
Мега Просте визначається як просте з щонайменше одним мільйоном десяткових знаків (титанічні прості містять щонайменше 1000 знаків, гігантське просте — 10000 знаків). Станом на 3 березня 2015 року відомо про 125 Мега Простих[2].
Підпроект MEGA фокусується на пошуку Мега Простих. Час перевірки на одному ядрі швидкого комп'ютера займає близько 1 години (Intel Haswell CPU). Пошук простих форми k·2n+1 було розпочато з n=3322000 для k<100, виключаючи k=3, 5, 7, 27. 18 липня 2014 року підпроект було перенесено з PRPNet в BOINC із зміною діапазонів пошуку з k<100 на 100<k<300.
PrimeGrid має намір продовжити пошук простих чисел Прота невизначено довго.
Результати підпроекту[ред. | ред. код]
Фактично не минає дня, щоб у підпроекті не було відшукано нових простих Прота. Серед усіх цих простих особливій інтерес викликають прості, що є дільниками чисел Ферма.
У табличці, що наведена нижче, представлені прості Прота, що було знайдено у PrimeGrid, що є дільниками чисел Ферма (станом на 14 лютого 2015 року):
Просте число | Цифр | Ділить | Дата | Автор |
---|---|---|---|---|
651·2476632+1 | 143 484 | F(476624) | 27.12.2008 | Eric Ueda |
519·2567235+1 | 170 758 | F(567233) | 06.03.2009 | Senji Yamashita |
659·2617815+1 | 185 984 | F(617813) | 31.03.2009 | Eric Embling |
7333·2138560+1 | 41 715 | F(138557) | 12.03.2011 | Dirk D'huyvetters |
9·22543551+1 | 765 687 | F(2543548) | 22.06.2011 | Scott Brown |
3771·2221676+1 | 66 736 | F(221670) | 01.07.2011 | Mark Doom |
4479·2226618+1 | 68 223 | F(226614) | 08.07.2011 | Peter Doggart |
25·22141884+1 | 644 773 | F(2141872) | 09.09.2011 | Grzegorz Granowski |
329·21246017+1 | 375 092 | F(1246013) | 04.01.2012 | Bruce Dodson |
131·21494099+1 | 449 771 | F(1494096) | 07.02.2012 | Rob Derrera |
7905·2352281+1 | 106 052 | F(352279) | 02.05.2012 | James Boerner |
1705·2906110+1 | 272 770 | F(906108) | 13.06.2012 | Robert Boniecki |
183·21747660+1 | 526 101 | F(1747656) | 10.03.2013 | Bart van Rooijen |
57·22747499+1 | 827 082 | F(2747497) | 13.05.2013 | Marshall Bishop |
2145·21099064+1 | 330 855 | F(1099061) | 18.06.2013 | Sai Yik Tang |
193·23329782+1 | 1 002 367 | F(3329780) | 25.07.2014 | Raymond Ottusch |
267·22662090+1 | 801 372 | F(2662088) | 13.02.2015 | Jay Parangalan |
Станом на 18 липня 2014 року підпроектом MEGA у PRPNet було знайдено 7 Мега Простих:
Просте число | Цифр | Дата | Автор |
---|---|---|---|
81·23352924+1 | 1 009 333 | 17.01.2012 | Michał Gasewicz |
87·23496188+1 | 1 052 460 | 28.03.2014 | Stefan Larsson |
51·23490971+1 | 1 050 889 | 28.03.2014 | Gary Craig |
93·23544744+1 | 1 067 077 | 06.05.2014 | Michał Gasewicz |
33·23570132+1 | 1 074 719 | 10.06.2014 | Fabrice Le Foulher |
35·23570777+1 | 1 074 913 | 10.06.2014 | Robert Lacroix |
35·23587843+1 | 1 080 050 | 04.07.2014 | Peter Tibbott |
Станом на 28 грудня 2017 року підпроектом Proth Mega Prime Search були знайдені наступні Мега Прості:
Прості підпроекту Proth Mega Prime Search | |||
---|---|---|---|
Просте число | Цифр | Дата | Автор |
9·23497442+1 | 1 052 836 | 23.10.2012 | Heinz Ming |
7·25775996+1 | 1 738 749 | 02.11.2012 | Martyn Elvy |
129·23328805+1 | 1 002 073 | 24.07.2014 | Eric Clifton |
193·23329782+1 | 1 002 367 | 25.07.2014 | Raymond Ottusch |
179·23371145+1 | 1 014 819 | 23.09.2014 | John Christy |
255·23395661+1 | 1 022 199 | 01.12.2014 | John Christy |
177·23411847+1 | 1 027 071 | 06.01.2015 | William Darney |
245·23411973+1 | 1 027 109 | 07.01.2015 | Rick Channing |
159·23425766+1 | 1 031 261 | 01.02.2015 | Evelyn Chew |
113·23437145+1 | 1 034 686 | 14.02.2015 | Evelyn Chew |
197·23477399+1 | 1 046 804 | 19.04.2015 | Tom Greer |
249·23486411+1 | 1 049 517 | 10.05.2015 | Evelyn Chew |
195·23486379+1 | 1 049 507 | 10.05.2015 | Naoki Yoshioka |
135·23518338+1 | 1 059 128 | 02.08.2015 | Evelyn Chew |
141·23529287+1 | 1 062 424 | 01.09.2015 | Chris Hoefliger |
191·23548117+1 | 1 068 092 | 30.10.2015 | Roman Azarenko |
251·23574535+1 | 1 076 045 | 25.01.2016 | Randall Scalise |
275·23585539+1 | 1 079 358 | 09.02.2016 | Tyler Bredl |
387·23322763+1 | 1 000 254 | 21.02.2016 | Sami Heikkilä |
189·23596375+1 | 1 082 620 | 24.02.2016 | Hiroyuki Okazaki |
323·23482789+1 | 1 048 427 | 20.06.2016 | Scott Brown |
329·23518451+1 | 1 059 162 | 21.06.2016 | Stefan Larsson |
345·23532957+1 | 1 063 529 | 22.06.2016 | William de Thomas |
351·23545752+1 | 1 067 381 | 22.06.2016 | Sylvanus A. Zimmerman |
381·23563676+1 | 1 072 776 | 23.06.2016 | Milan Fňašek |
309·23577339+1 | 1 076 889 | 24.06.2016 | Russell Mathers |
403·23334410+1 | 1 003 716 | 25.06.2016 | Roman Trunov |
453·23387048+1 | 1 019 606 | 14.07.2016 | Andreas Mueller |
479·23411975+1 | 1 027 110 | 25.07.2016 | Matt Jurach |
453·23461688+1 | 1 042 075 | 23.08.2016 | Randall Scalise |
491·23473837+1 | 1 045 732 | 29.08.2016 | Stephen Norton |
495·23484656+1 | 1 048 989 | 05.09.2016 | Randall Scalise |
447·23533656+1 | 1 063 740 | 28.09.2016 | Stefan Geiger |
465·23536871+1 | 1 064 707 | 30.09.2016 | Kenneth Biscop |
415·23559614+1 | 1 071 554 | 08.10.2016 | Randall Scalise |
597·23322871+1 | 1 000 287 | 21.10.2016 | Randall Scalise |
791·23323995+1 | 1 000 626 | 24.10.2016 | Randall Scalise |
555·23325925+1 | 1 001 206 | 30.10.2016 | Alexander Falk |
821·23327003+1 | 1 001 531 | 02.11.2016 | Randall Scalise |
659·23327371+1 | 1 001 642 | 03.11.2016 | Dejana Ristic |
655·23327518+1 | 1 001 686 | 04.11.2016 | Paul Mazumdar |
673·23330436+1 | 1 002 564 | 12.11.2016 | Randall Scalise |
611·23334875+1 | 1 003 901 | 27.11.2016 | John S. Chambers |
849·23335669+1 | 1 004 140 | 29.11.2016 | Randall Scalise |
651·23337101+1 | 1 004 571 | 03.12.2016 | Konstantin Stanko |
733·23340464+1 | 1 005 583 | 12.12.2016 | Randall Scalise |
543·23351686+1 | 1 008 961 | 16.01.2017 | Simon Rawles |
1183·23353058+1 | 1 009 375 | 19.01.2017 | Michele T. Mazzucato |
619·23362814+1 | 1 012 311 | 09.02.2017 | Daniel Frużyński |
533·23362857+1 | 1 012 324 | 09.02.2017 | Hans-Jürgen Bergelt |
777·23367372+1 | 1 013 683 | 17.02.2017 | Lars Fricke |
617·23368119+1 | 1 013 908 | 18.02.2017 | Kimmo Koski |
715·23368210+1 | 1 013 936 | 18.02.2017 | Daniel Frużyński |
677·23369115+1 | 1 014 208 | 20.02.2017 | Wolfgang Schmidt |
861·23377601+1 | 1 016 763 | 12.03.2017 | Mike Kinney |
1093·23378000+1 | 1 016 883 | 14.03.2017 | Andreas Rohmann |
621·23378148+1 | 1 016 927 | 14.03.2017 | Randall Scalise |
663·23390469+1 | 1 020 636 | 23.04.2017 | Rolf Henrik Nilsson |
805·23391818+1 | 1 021 042 | 28.04.2017 | Reiner Elgetz |
555·23393389+1 | 1 021 515 | 03.05.2017 | Douglas B. McKay |
1049·23395647+1 | 1 022 195 | 12.05.2017 | Randall Scalise |
609·23392301+1 | 1 021 188 | 29.04.2017 | «jimmy» |
611·23398273+1 | 1 022 985 | 22.05.2017 | Randall Scalise |
1167·23399748+1 | 1 023 430 | 27.05.2017 | Eric Eskam |
833·23403765+1 | 1 024 639 | 13.06.2017 | Randall Scalise |
953·23405729+1 | 1 025 230 | 20.06.2017 | Randall Scalise |
907·23417890+1 | 1 028 891 | 05.08.2017 | Randall Scalise |
999·23418885+1 | 1 029 190 | 09.08.2017 | Randall Scalise |
975·23419230+1 | 1 029 294 | 10.08.2017 | Eric Eskam |
1005·23420846+1 | 1 029 781 | 18.08.2017 | Łukasz Piotrowski |
1119·23422189+1 | 1 030 185 | 24.08.2017 | Jochen Beck |
1127·23427219+1 | 1 031 699 | 15.09.2017 | Randall Scalise |
911·23432643+1 | 1 033 331 | 05.10.2017 | Jochen Beck |
1147·23435970+1 | 1 034 334 | 17.10.2017 | Randall Scalise |
625·23438572+1 | 1 035 117 | 27.10.2017 | Jochen Beck |
543·23438810+1 | 1 035 188 | 29.10.2017 | Randall Scalise |
943·23440196+1 | 1 035 606 | 02.11.2017 | Lukáš Hron |
943·23442990+1 | 1 036 447 | 13.11.2017 | Joshua Charles Campbell |
1155·23446253+1 | 1 037 429 | 27.11.2017 | Randall Scalise |
1065·23447906+1 | 1 037 927 | 03.12.2017 | Juan C. Toledo |
1155·23455254+1 | 1 040 139 | 28.12.2017 | Josh Closs |
З 2018 року у проекті відбулась зміна політики анонсування відкриттів визначних простих чисел. Лише числа, що потрапляють у топ 100 простих, анонсуються.
Seventeen or Bust[ред. | ред. код]
Числом Серпінського називається таке непарне натуральне число k, що для довільного натурального n число k·2n+1 не є простим.
Послідовність відомих чисел Серпінського починається:
78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909, 965431, …
Те, що число 78557 є числом Серпінського, було доведено в 1962 році Джоном Селфриджем[en] (англ. John Selfridge), який виявив, що кожне число виду 78557·2n+1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 19, 37, 73}.
Проблему Серпінського можна сформулювати так: «Яким є найменше число Серпінського?»
Більшість знавців теорії чисел вірять, що 78557 є найменшим числом Серпінського. Щоб це довести, достатньо показати, що для кожного непарного k, такого, що 0<k<78557, існує таке n, що число k·2n+1 є простим.
Підпроект Seventeen or Bust працює над проблемою Серпінського. Проект так називається, бо до його початку не біло відомо, чи існують прості для 17-ти чисел k. Наразі залишається знайти прості числа для 5-ти k, інші k, для яких відомі прості k·2n+1, наведено в таблиці:
№ | k | Просте число | Цифр | Дата | Автор |
---|---|---|---|---|---|
1 | 4847 | 4847·23321063+1 | 999 744 | 15.10.2005 | Richard Hassler |
2 | 5359 | 5359·25054502+1 | 1 521 561 | 06.12.2003 | Randy Sundquist |
3 | 10223 | 10223·231172165+1 | 9 383 761 | 31.10.2016 | Szabolcs Peter |
4 | 19249 | 19249·213018586+1 | 3 918 990 | 26.03.2007 | Константин Агафонов |
5 | 21181 | ||||
6 | 22699 | ||||
7 | 24737 | ||||
8 | 27653 | 27653·29167433+1 | 2 759 677 | 08.06.2005 | Derek Gordon |
9 | 28433 | 28433·27830457+1 | 2 357 207 | 30.12.2004 | анонімний учасник |
10 | 33661 | 33661·27031232+1 | 2 116 617 | 13.10.2007 | Sturle Sunde |
11 | 44131 | 44131·2995972+1 | 299 823 | 05.12.2002 | deviced (нік) |
12 | 46157 | 46157·2698207+1 | 210 186 | 27.11.2002 | Stephen Gibson |
13 | 54767 | 54767·21337287+1 | 402 569 | 22.12.2002 | Peter Coels |
14 | 55459 | ||||
15 | 65567 | 65567·21013803+1 | 305 190 | 03.12.2002 | James Burt |
16 | 67607 | ||||
17 | 69109 | 69109·21157446+1 | 348 431 | 07.12.2002 | Sean DiMichele |
Результати підпроекту[ред. | ред. код]
Прості підпроекту SoB, що було знайдено у PrimeGrid (станом на 31 жовтня 2016 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
10223·231172165+1 | 9 383 761 | 31.10.2016 | Szabolcs Peter |
Sierpinski/Riesel Base 5 Problem[ред. | ред. код]
Проблема Серпінського/Різеля за основою 5[ред. | ред. код]
Цей підпроект є поширенням проблеми Серпінського/Різеля (SoB/TRP). Він намагається розв'язати проблему Серпінського/Різеля за основою 5, віднайти найменше число Серпінського/Різеля. Таким чином відшукуються прості виду k·5n±1 з парними значеннями k.
Числа Серпінського за основою 5[ред. | ред. код]
Гіпотеза полягає у тому, що найменшим парним числом Серпінського за основою 5 є k = 159986. Щоб довести це, достатньо показати, що існує просте число виду k·5n+1 для кожного парного k < 159986. Наразі це доведено для всіх парних k, окрім наступних 31 значення (станом на 26 квітня 2019 року): k = 6436, 7528, 10918, 26798, 29914, 31712, 36412, 41738, 44348, 44738, 45748, 51208, 58642, 60394, 62698, 64258, 67612, 67748, 71492, 74632, 76724, 83936, 84284, 90056, 92906, 93484, 105464, 118568, 126134, 139196, 152588
Числа Різеля за основою 5[ред. | ред. код]
Гіпотеза полягає у тому, що найменшим парним числом Різеля за основою 5 є k=346802. Щоб довести це, достатньо показати, що існує просте число виду k·5n−1 для кожного парного k < 346802. Наразі це доведено для всіх парних k, окрім наступних 67 значень (станом на 23 червня 2019 року): k = 3622, 4906, 23906, 26222, 35248, 35816, 52922, 63838, 64598, 68132, 71146, 76354, 81134, 92936, 102818, 102952, 109238, 109838, 109862, 127174, 131848, 134266, 136804, 143632, 145462, 145484, 146264, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 177742, 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 207494, 213988, 231674, 238694, 239062, 239342, 246238, 248546, 259072, 265702, 267298, 271162, 273662, 285598, 285728, 298442, 304004, 313126, 318278, 325922, 335414, 338866
Історія[ред. | ред. код]
17 вересня 2004 року на сторінках yahoo групи primeform Роберт Сміт (Robert Smith) вперше презентував ідею пошуку найменших чисел Серпінського/Різеля за основою 5. Використовуючи покриваючу множину {3, 7, 13, 31, 601}, він висунув гіпотезу, що k=346802 є найменшим числом Різеля за основою 5. Невдовзі Гвідо Сметрійнз (Guido Smetrijns) запропонував k=159986 як найменше число Серпінського за основою 5.
Після виконання великої частини самостійних обрахунків, Роберт оголосив про це на форумі mersenneforum.org 28 вересня 2004 року, і таким чином, зусилля з розподіленого обчислення було розпочато. Іншими важливими гравцями у справі розробки, управління і розвитку проекту є Lars Dausch, Geoff Reynolds, Anand S Nair, і Thomas Masser.
Результати підпроекту[ред. | ред. код]
Прості, що було знайдено у PrimeGrid (станом на 23 червня 2019 року):
Прості підпроекту SR5 | |||
---|---|---|---|
Просте число | Цифр | Дата | Автор |
301016·5586858−1 | 410 202 | 24.01.2011 | Puzzle Peter |
210092·5618136−1 | 432 064 | 31.01.2011 | Puzzle Peter |
266206·5608649−1 | 425 433 | 10.02.2011 | Puzzle Peter |
270748·5614625−1 | 429 610 | 14.02.2011 | Puzzle Peter |
49568·5640900−1 | 447 975 | 01.07.2011 | Sascha Beat Dinkel |
262172·5643342−1 | 449 683 | 13.07.2011 | Kimmo Myllyvirta |
27994·5645221−1 | 450 995 | 18.07.2011 | Philipp Bliedung |
331882·5674961−1 | 471 784 | 11.11.2011 | Ronny Willig |
2488·5679769−1 | 475 142 | 24.11.2011 | Sascha Beat Dinkel |
72532·5708453−1 | 495 193 | 07.02.2012 | Göran Schmidt |
5374·5723697−1 | 505 847 | 13.04.2012 | Kelvin Lewis |
18656·5735326−1 | 513 976 | 03.05.2012 | Lennart Vogel |
338948·5743996−1 | 520 037 | 07.05.2012 | Ricky L Hubbard |
340168·5753789−1 | 526 882 | 18.05.2012 | Kimmo Myllyvirta |
316594·5766005−1 | 535 421 | 30.05.2012 | Michael Becker |
11812·5769343−1 | 537 752 | 02.06.2012 | Göran Schmidt |
289184·5770116−1 | 538 294 | 07.06.2012 | David Yost |
162668·5785748−1 | 549 220 | 03.07.2012 | Lennart Vogel |
48764·5831946−1 | 581 510 | 12.10.2012 | David Yost |
57406·5844253−1 | 590 113 | 07.11.2012 | David Yost |
174344·5855138−1 | 597 722 | 09.01.2013 | Ronny Willig |
162434·5856004−1 | 598 327 | 10.01.2013 | Predrag Kurtovic |
110488·5917100+1 | 641 031 | 25.03.2013 | Ronny Willig |
102976·5929801−1 | 649 909 | 09.05.2013 | David Yost |
70082·5936972−1 | 654 921 | 30.05.2013 | Scott Brown |
243686·51036954−1 | 724 806 | 16.06.2013 | Katsumi Hirai |
55154·51063213+1 | 743 159 | 16.06.2013 | Senji Yamashita |
97768·5987383−1 | 690 157 | 17.06.2013 | Ulrich Hartel |
130484·51080012−1 | 754 902 | 17.06.2013 | Randy Ready |
305716·51093095−1 | 764 047 | 18.06.2013 | Randy Ready |
329584·51122935−1 | 784 904 | 21.06.2013 | Stephen R Cilliers |
92182·51135262+1 | 793 520 | 21.06.2013 | Randy Ready |
17152·51131205−1 | 790 683 | 22.06.2013 | Bob Benson |
1396·51146713−1 | 801 522 | 23.06.2013 | Randy Ready |
150344·51205508−1 | 842 620 | 28.06.2013 | Randy Ready |
97366·51259955−1 | 880 676 | 04.07.2013 | Jörg Meili |
243944·51258576−1 | 879 713 | 05.07.2013 | Tod Slakans |
268514·51292240−1 | 903 243 | 16.07.2013 | Raymond Schouten |
256612·51335485−1 | 933 470 | 04.08.2013 | Wolfgang Schwieger |
175124·51422646−1 | 994 393 | 31.10.2013 | David Yost |
245114·51424104−1 | 995 412 | 01.11.2013 | David Yost |
173198·51457792−1 | 1 018 959 | 04.12.2013 | Motohiro Ohno |
37292·51487989+1 | 1 040 065 | 29.12.2013 | Stephen R Cilliers |
59912·51500861+1 | 1 049 062 | 17.01.2014 | Raymond Ottusch |
178658·51525224−1 | 1 066 092 | 31.01.2014 | Keishi Toda |
22934·51536762−1 | 1 074 155 | 06.02.2014 | Keishi Toda |
330286·51584399−1 | 1 107 453 | 21.03.2014 | Scott Brown |
104944·51610735−1 | 1 125 861 | 09.04.2014 | Brian Smith |
207394·51612573−1 | 1 127 146 | 09.04.2014 | Honza Cholt |
326834·51634978−1 | 1 142 807 | 25.04.2014 | Scott Brown |
22478·51675150−1 | 1 170 884 | 19.06.2014 | Guo Hua Miao |
138172·51714207−1 | 1 198 185 | 27.06.2014 | Walter Darimont |
24032·51768249+1 | 1 235 958 | 23.07.2014 | Hiroyuki Okazaki |
133778·51785689+1 | 1 248 149 | 17.08.2014 | Guo Hua Miao |
325918·51803339−1 | 1 260 486 | 21.09.2014 | Jörg Meili |
109208·51816285+1 | 1 269 534 | 18.10.2014 | Scott Brown |
144052·52018290+1 | 1 410 730 | 23.05.2015 | Wolfgang Schmidt |
100186·52079747−1 | 1 453 686 | 21.10.2015 | Toshitaka Kumagai |
154222·52091432+1 | 1 461 854 | 10.11.2015 | Scott Brown |
306398·52112410−1 | 1 476 517 | 11.01.2016 | André Ahlfors Dahl |
77072·52139921+1 | 1 495 746 | 06.03.2016 | Wolfgang Becker |
92158·52145024+1 | 1 499 313 | 15.03.2016 | Karl Burridge |
296024·52185270−1 | 1 527 444 | 25.03.2016 | Steven Wong |
53546·52216664−1 | 1 549 387 | 30.05.2016 | Tom Greer |
180062·52249192−1 | 1 572 123 | 20.08.2016 | Stefan Larsson |
171362·52400996−1 | 1 678 230 | 25.08.2017 | Frank Schwegler |
301562·52408646−1 | 1 683 577 | 17.09.2017 | Håkan Lind |
327926·52542838−1 | 1 777 374 | 19.06.2018 | Selya Tsuji |
81556·52539960+1 | 1 775 361 | 20.06.2018 | Jiří Bočan |
66916·52628609−1 | 1 837 324 | 29.07.2018 | Honza Cholt |
194368·52638045−1 | 1 843 920 | 15.08.2018 | Honza Cholt |
138514·52771922+1 | 1 937 496 | 26.04.2019 | Ken Ito |
88444·52799269−1 | 1 956 611 | 21.06.2019 | Scott Brown |
322498·52800819−1 | 1 957 694 | 23.06.2019 | Jordan Romaidis |
Sophie Germain Prime Search[ред. | ред. код]
Просте число p називається простим Софі Жермен, якщо число 2·p+1 також є простим. Наприклад просте число 5 є простим Софі Жермен, адже число 2·5+1 = 11 також є простим. Ці числа названі числами Софі Жермен на честь екстраординарної французької математички, що зробила важливий внесок в галузі диференційної геометрії і теорії чисел та у вивчені Останньої Теореми Ферма.
В підпроекті Sophie Germain Prime Search спочатку перевіряється на простоту число виду k·2n−1. Якщо воно є простим, тоді перевіряються числа k·2n+1, k·2n-1−1 та k·2n+1−1. Якщо виявиться, що простим є також k·2n-1−1 або k·2n+1−1 — це означає, що знайдено просте Софі Жермен. Якщо простим виявиться k·2n+1, тоді можна сказати, що знайдено прості числа-близнюки. Можливість знайти просте Софі Жермен або прості-близнюки робить пошук саме у цьому підпроекті привабливішим.
Результати підпроекту[ред. | ред. код]
Прості Софі Жермен, що було знайдено у PrimeGrid (станом на 29 лютого 2016 року):
Просте число SGS | 2p+1 | Цифр | Дата | Автор |
---|---|---|---|---|
18543637900515·2666667−1 | 18543637900515·2666668−1 | 200 701 | 09.04.2012 | Philipp Bliedung |
2618163402417·21290000−1 | 2618163402417·21290001−1 | 388 342 | 29.02.2016 | Scott Brown |
Прості-близнюки, що було знайдено у PrimeGrid (станом на 14 вересня 2016 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
3756801695685·2666669±1 | 200 700 | 25.12.2011 | Timothy D. Winslow |
2996863034895·21290000±1 | 388 342 | 14.09.2016 | Tom Greer |
The Riesel Problem[ред. | ред. код]
Ганс Івар Різель (англ. Hans Ivar Riesel, нар. 1929 у Стокгольмі) — шведський математик, у 1956 показав, що існує нескінчено велика кількість додатніх непарних чисел k таких, що k·2n−1 є числом складеним для будь-якого цілого n ≥ 1. Такі числа тепер отримали назву чисел Різеля. Він також показав, що число k = 509203 є одним з таких. А також 509203 плюс будь-яке натуральне число, помножене на 11184810. Кожне число виду 509203·2n−1 ділиться принаймні на одне число із множини {3, 5, 7, 13, 17, 241}.
Існує гіпотеза, що 509203 є найменшим числом Різеля. Проблема Різеля полягає у тому, щоб довести, що 509203 є найменшим числом Різеля. Щоб показати, що це число є найменшим, достатньо віднайти просте число для кожного додатнього непарного k, меншого за 509203. Станом на 13 грудня 2017 року залишається віднайти прості для 49 чисел k:
2293, 9221, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 146561, 161669, 192971, 206039, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743
Результати підпроекту[ред. | ред. код]
Прості, що було знайдено у PrimeGrid (станом на 5 жовтня 2014 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
191249·23417696−1 | 1 028 835 | 21.11.2010 | Jonathan Pritchard |
428639·23506452−1 | 1 055 553 | 14.01.2011 | Brett Melvold |
65531·23629342−1 | 1 092 546 | 05.04.2011 | Adrian Schori |
123547·23804809−1 | 1 145 367 | 08.05.2011 | Jakub Łuszczek |
415267·23771929−1 | 1 135 470 | 08.05.2011 | Alexey Tarasov |
141941·24299438−1 | 1 294 265 | 26.05.2011 | Scott Brown |
353159·24331116−1 | 1 303 802 | 31.05.2011 | Jaakko Reinman |
162941·2993718−1 | 299 145 | 02.02.2012 | Dmitry Domanov |
252191·25497878−1 | 1 655 032 | 23.06.2012 | Jan Haller |
398023·26418059−1 | 1 932 034 | 05.11.2013 | Vladimir Volynsky |
304207·26643565−1 | 1 999 918 | 10.11.2013 | Randy Ready |
40597·26808509−1 | 2 049 571 | 25.12.2013 | Frank Meador |
402539·27173024−1 | 2 159 301 | 02.10.2014 | Walter Darimont |
502573·27181987−1 | 2 162 000 | 04.10.2014 | Denis Iakovlev |
273809·28932416−1 | 2 688 931 | 13.12.2017 | Wolfgang Schwieger |
Twin Prime Search[ред. | ред. код]
Twin Prime Search (TPS) — підпроект, що займався пошуком великих простих-близнюків (twin primes). Підпроект використовує програму LLR (для тестування на простоту) та NewPGen (для відсіву), був розпочатий 13 квітня 2006 Майклом Квоком (Michael Kwok).
До цього часу не відомо, чи існує нескінченно багато простих-близнюків.
Проектом TPS було знайдено рекордні прості-близнюки 2003663613·2195000±1 15 січня 2007 році на комп'ютері користувача Eric Vautier. Ці числа складаються з 58711 цифри, що зробило їх найбільшими відомими на той час простими-близнюками. Проект працював у співпраці з PrimeGrid, що зробив більшість LLR тестів.
6 серпня 2009 року 2 проекта (PrimeGrid та Twin Prime Search) оголосили, що рекорд простих-близнюків поновлено. Це прості 65516468355·2333333±1 і складаються з 100355 цифр. Найменше з цих двох простих станом на серпень 2009 також є найбільшим з відомих простих Чена.
Woodall Prime Search[ред. | ред. код]
Woodall Prime Search — це підпроект з пошуку простих чисел Вудала. В теорії чисел число Вудала (що інколи називають числами Каллена другого порядку) — натуральне число виду Wn = n·2n−1
Експоненти n, для яких відповідні числа Вудала прості, утворюють послідовність:
2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462, 512, 751, 822, 5312, 7755, 9531, 12379, 15822, 18885, 22971, 23005, 98726, 143018, 151023, 667071, 1195203, 1268979, 1467763, 2013992, 2367906, 3752948, 17016602
В 1976 році Христофер Хулей (англ. Christopher Hooley) показав, що майже всі числа Каллена складені. Доведення Христофера Хулей було перероблено математиком Хірмі Суяма, щоб показати, що воно вірне для будь-якої послідовності n·2n+a+b, де a і b — цілі числа, а також частково для чисел Вудала.
Є гіпотеза, що простих чисел Вудала є нескінчено багато.
Результати підпроекту[ред. | ред. код]
Прості числа Вудала, що було знайдено у PrimeGrid (станом на 21 березня 2018 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
2013992·22013992−1 | 606 279 | 04.08.2007 | Lasse Mejling Andersen |
2367906·22367906−1 | 712 818 | 13.08.2007 | Stephen Kohlman |
3752948·23752948−1 | 1 129 757 | 21.12.2007 | Matthew J. Thompson |
17016602·217016602−1 | 5 122 515 | 21.03.2018 | Diego Bertolotti |
Підпроекти PRP[ред. | ред. код]
Метою проектів PRP (англ. PRobably Prime) є пошук ймовірно простих чисел, що вимагають додаткової перевірки на простоту методом LLR.
Generalized Fermat Prime Search[ред. | ред. код]
Це підпроект з пошуку узагальнених простих чисел Ферма виду bn+1, де n є ступінню 2.
Про узагальнені прості Ферма[ред. | ред. код]
Протягом XVII сторіччя П'єр Ферма (Pierre de Fermat) та Марен Мерсенн (Marin Mersenne) вивчали дві певні форми чисел, з надією, що вони можуть продукувати велику кількість простих чисел, чи навіть нескінчену кількість простих. Мерсенн працював над переліком простих виду 2n−1, таких, що n < 257. Знадобилось багато років праці, щоб створити коректний перелік таких чисел. У листуванні з Френікл (Frénicle) Ферма висловив переконання, якщо n є ступінню 2, тоді 2n+1 є простим числом. Ферма знав, що 3, 5, 17, 257 і 65537 є простими, але пізніше Леонард Ейлер (Leonhard Euler) показав, що Ферма помилявся, віднайшовши дільник для наступного числа.
На честь натхнених піонерів теорії чисел, числа виду 2n−1 тепер називаються числами Мерсенна, а числа виду 2n+1 числами Ферма. Пошук простих Мерсенна та Ферма значно просунувся від часів XVII сторіччя. Тепер відомі всі прості Мерсенна з кількістю цифр менше за 2'000'000 і досліджено всі числа Ферма аж до 2'000'000'000 цифр! Це стало можливим, тому що протягом XIX ст. було винайдено декілька ефектнивних методів перевірки цих чисел на простоту. Одночасно з цим, деякі тести не менш швидкі були знайдені для перевірки всіх чисел N, якщо відома факторизація чисел N−1 або N+1. Таким чином багато форм чисел можуть бути використані для пошуку найбільших відомих простих, але на диво пошук найбільших простих обмежується числами Мерсенна. Відомими виключенями стали (2148+1)/17 (винайдено у 1951 році з використанням ручного обчислювального методу), 180·(2127−1)2+1 (винайдено у 1951 році) і 391581·2216193−1 (знайдено за допомогою «Amdahl 6» в 1989).
З 50-х по 70-ті розмір найбільших відомих простих постійно ріс разом із швидкостями комп'ютерів, але використовувані алгоритми залишались тими самими, що і наприкінці XIX ст. Але в 80-х роках XX ст., методи, що використовуються для обчислення базової операції алгоритму, добутку, змінилась. Помітивши, що добуток може бути представлений у вигляді суми скінченої послідовності, теорія дискретних транформація показала, як швидко обчислити цю операцію за допомогою швидких перетворень Фур'є (Fast Fourier Transform, FFT). За допомогою цього методу було знайдено деякі прості з більш ніж 10'000 та 100'000 цифр.
В 1994 R. Crandall та B. Fagin винайшли, що за допомогою дискретних зважених трансформацій (Discrete Weighted Transform, DWT) швидкість пошуку простих Мерсенна та Ферма може бути подвоєна. Цей метод було використано у пошуку шости нових простих Мерсена (найбільше з них містило понад 6'000'000 цифр) і довести складеність деяких чисел Ферма. Але прості серед чисел Мерсена та Ферма є рідкістю і шанс знайти нове просте малий.
В 1998 році Y. Gallot помітив, що дискретна зважена трансформація є поліноміальною операцією і якщо представлення чисел не обмежується базою 2, тоді багато чисел можуть бути перевірені на тому ж рівні швидкості, як і числа Мерсенна: узагальнені числа Ферма (Generalized Fermat Numbers, GFN), які є числами виду bn+1, де n є ступінню 2. Він реалізував алгоритм в 1999 у програмі Proth.exe, яка з того часу була ще оптимізована. Теоретичні гіпотези стали дійсністю: пошук узагальнених простих Ферма так само швидкий, як і пошук простих Мерсенна такого ж розміру. За допомогою десятків комп'ютерів було знайдено багато простих, що містять більше ніж 100'000 цифр. У 2002 P. Carmody разом з B. Frey досягли великих успіхів в алгоритмі відсіву узагальнених чисел Ферма. P. Carmody організував прикладання великих зусиль до відсіву за допомогою програми, що була написана D. Underbakke, що таким чином прискорило пошук узагальнених простих чисел Ферма.
Узагальнених чисел Ферма існує набагато більше, ніж чисел Мерсенна того ж розміру і багато з них чекають на те, щоб заповнити прогалини між простими Мерсена, що вже знайдено і тими, що ще ні. Якщо ви зацікавлені у пошуку простих XXI сторіччя, вас запрошують долучитися до Generalized Fermat Prime Search!
Результати підпроекту[ред. | ред. код]
Мега прості GFN (b2n+1, де n≥18), що було знайдено у PrimeGrid (станом на 18 вересня 2019 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
10590941048576+1 | 6 317 602 | 31.10.2018 | Rob Gahan |
9194441048576+1 | 6 253 210 | 29.08.2017 | Sylvanus A. Zimmerman |
2985036524288+1 | 3 394 739 | 18.09.2019 | Peter Harvey |
2877652524288+1 | 3 386 397 | 29.06.2019 | Roman Vogt |
2788032524288+1 | 3 379 193 | 17.04.2019 | Ed Goforth |
2733014524288+1 | 3 374 655 | 18.03.2019 | Yair Givoni |
2312092524288+1 | 3 336 572 | 04.08.2018 | Rob Gahan |
2061748524288+1 | 3 310 478 | 20.03.2018 | Cesare Marini |
1880370524288+1 | 3 289 511 | 15.01.2018 | Scott Brown |
475856524288+1 | 2 976 633 | 08.08.2012 | Masashi Kumagai |
356926524288+1 | 2 911 151 | 20.06.2012 | (bherbihyewrbg) |
341112524288+1 | 2 900 832 | 15.06.2012 | Peyton Hayslette |
75898524288+1 | 2 558 647 | 19.11.2011 | Michael Goetz |
8521794262144+1 | 1 816 798 | 09.09.2019 | Ken Ito |
6291332262144+1 | 1 782 250 | 14.12.2018 | Karsten Freihube |
6287774262144+1 | 1 782 186 | 12.12.2018 | Greg Miller |
5828034262144+1 | 1 773 542 | 26.09.2018 | Rob Gahan |
5205422262144+1 | 1 760 679 | 17.06.2018 | Scott Brown |
5152128262144+1 | 1 759 508 | 05.06.2018 | Rob Gahan |
4489246262144+1 | 1 743 828 | 01.03.2018 | Wolfgang Schwieger |
4246258262144+1 | 1 737 493 | 15.02.2018 | Rob Gahan |
3933508262144+1 | 1 728 783 | 27.01.2018 | Alen Kecic |
3853792262144+1 | 1 726 452 | 10.01.2018 | Rod Skinner |
3673932262144+1 | 1 721 010 | 03.12.2017 | Sean Humphries |
3596074262144+1 | 1 718 572 | 16.11.2017 | Howard Gordon |
3547726262144+1 | 1 717 031 | 30.10.2017 | Scott Brown |
3060772262144+1 | 1 700 222 | 30.06.2017 | Sean Humphries |
2676404262144+1 | 1 684 945 | 22.03.2017 | Wolfgang Schwieger |
2611204262144+1 | 1 682 141 | 11.03.2017 | Roman Vogt |
2514168262144+1 | 1 677 825 | 24.02.2017 | William de Thomas |
2042774262144+1 | 1 654 187 | 24.11.2016 | Tsuyoshi Ohsugi |
1828858262144+1 | 1 641 593 | 10.08.2016 | Brook Harste |
1615588262144+1 | 1 627 477 | 04.05.2016 | Brook Harste |
1488256262144+1 | 1 618 131 | 05.03.2016 | Stefan Larsson |
1415198262144+1 | 1 612 400 | 16.02.2016 | Frank Matillek |
773620262144+1 | 1 543 643 | 19.04.2012 | Senji Yamashita |
676754262144+1 | 1 528 413 | 12.02.2012 | Carlos Loureiro |
525094262144+1 | 1 499 526 | 18.01.2012 | David Tomecko |
361658262144+1 | 1 457 075 | 29.10.2011 | Michel Johnson |
145310262144+1 | 1 353 265 | 08.02.2011 | Ricky L Hubbard |
40734262144+1 | 1 208 473 | 08.03.2011 | Senji Yamashita |
Підпроекти Sieve[ред. | ред. код]
Підпроекти Sieve (з англ. sieve — відсів) займаються відсіюванням кандидатів для підпроектів LLR. Відсів складених кандидатів може бути набагато ефективніше за перевірку на простоту методом LLR. Із часом, коли глибина відсіву росте, ефективність відсіву падає і видалення складених чисел із кандидатів на простоту відбувається все рідше. Коли середній час на відсів кандидатів стає спвіставний з середнім часом на перевірку методом LLR, доцільність використання відсіву втрачається.
321 Prime Search Sieve[ред. | ред. код]
Підпроект 321 Prime Search Sieve займається відсівом для підпроекту 321 Prime Search
Наразі підпроект поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.
Cullen/Woodall Sieve[ред. | ред. код]
Підпроект Cullen/Woodall Sieve займається відсівом для Cullen та Woodall Prime Search
Наразі підпроект поставлено на паузу, оптимальна глибина відсіву у 2500T була досягнута навесні 2012.
Generalized Cullen/Woodall Sieve[ред. | ред. код]
Підпроект Generalized Cullen/Woodall Sieve займається відсівом для Generalized Cullen/Woodall Prime Search
Proth Prime Search Sieve[ред. | ред. код]
Підпроект Proth Prime Search Sieve займається відсівом для Proth Prime Search
Sierpinski (ESP/PSP/SoB) Sieve[ред. | ред. код]
Підпроект об'єднує зусилля з відсіву для підпроектів Seventeen or Bust, Prime Sierpinski Project, Extended Sierpinski Project
Відсів для Seventeen or Bust та Prime Sierpinski Project поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.
Відсів Extended Sierpinski Project Sieve для Extended Sierpinski Project розпочато 29 червня 2014 року.
Наразі підпроект поставлено на паузу, оптимальна глибина відсіву для Extended Sierpinski Project була досягнута у червні 2016 року.
The Riesel Problem Sieve[ред. | ред. код]
Підпроект The Riesel Problem Sieve займається відсівом для The Riesel Problem
Наразі підпроект поставлено на паузу, оскільки була досягнута оптимальна глибина відсіву.
Project Staging Area (PSA)[ред. | ред. код]
Від початку PSA було створено задля дослідження, тестування та підготовки майбутніх BOINC підпроектів для PrimeGrid. У PSA досі ведеться пошук простих чисел інших форм, яких немає в підпроектах BOINC. Існує два напрямки участі у PSA — PRPNet та Manual Sieving:
- PRPNet було розроблено Марком Роденкірхом (англ. Mark Rodenkirch), PRPNet дуже подібний до BOINC, але використовується тільки для пошуку простих чисел. PRPNet не має (інтерфейсної оболонки). Натомість він стартує або в DOS вікні (Windows) або в командному терміналі (Linux). Все досить просто — скачай, розпакуй файл для твоєї ОС, відредагуй декілька рядків у файлі prpclient.ini і запускай.
- Ручний відсів (Manual Sieving) — гарний відсів веде до кращого результату під час перевірки чисел на простоту. Деякі пошуки вимагають досить значних зусиль, тому для таких відсівів залучається спільнота. Є ділька проектів, що координуються за допомогою постингу на форумі.
За участь в PSA існує ручна процедура нарахування очок в віртуальний підпроект PSA в BOINC.
Підпроекти PRPNet[ред. | ред. код]
- 121 Prime Search
- server=121:0:1:prpnet.primegrid.com:12001
- 27 Prime Search
- server=27:0:1:prpnet.primegrid.com:12006
- Factorial Prime Search
- server=FPS:0:1:prpnet.primegrid.com:12002
- Primorial Prime Search
- server=PRS:0:1:prpnet.primegrid.com:12008
- Wieferich Prime Search (ПРИЗУПИНЕНО)
- server=WIEFERICH:0:2:prpnet.primegrid.com:13000
- Wall-Sun-Sun Prime Search (ПРИЗУПИНЕНО)
- server=WALLSUNSUN:0:2:prpnet.primegrid.com:13001
Підпроекти Manual Sievieng[ред. | ред. код]
- Factorial Prime Search (Manual Sieve)
- Primorial Prime Search (Manual Sieve)
- Sierpinski/Riesel base 5 Project (Manual Sieve)
- Generalized Fermat Prime Search (Manual Sieve)
- PPS/RSP (Manual Sieve)
Бейджики[ред. | ред. код]
PrimeGrid нагороджує користувачів, що досягли певного рівня зароблених очок, бейджиками. Ці відзнаки не дають нікому ніякої переваги, але багато хто сприймає бейджі як знак певного досягнення. Нагорода бейджами використовується також для заохочення участі у менш популярних підпроектах. Поточні рівні бейджів: Бронза (10'000) / Срібло (100'000) / Золото (500'000) / Аметист (1'000'000) / Рубін (2'000'000) / Бірюза (5'000'000) / Нефрит (10'000'000) / Сапфір (20'000'000) / Смарагд (50'000'000) / Подвійна Бронза (100'000'000) / Подвійне Срібло (200'000'000) / Подвійне Золото (500'000'000) / Подвійний Аметист (1'000'000'000) / Подвійний Рубін (2'000'000'000) / Подвійна Бірюза (5'000'000'000) / Подвійний Нефрит (10'000'000'000) / Подвійний Сапфір (20'000'000'000) / Подвійний Смарагд (50'000'000'000)
Підпроект | Бейджики | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
321 LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
321 Sieve | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
AP | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Cullen LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
CW Sieve | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
ESP LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
GCW LLR | ||||||||||||||||||
GCW Sieve | ||||||||||||||||||
GFN | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
PSP LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
PSP Sieve | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
PSA | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
PPS LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
PPS Sieve | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
SOB LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
SGS LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
SR5 LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
TRP LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
TRP Sieve | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
TPS LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Woodall LLR | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
До квітня 2014 року між підпроектами LLR та AP26/Sieve/GFN/PSA існувала різниця у рівнях для бейджиків одного кольору. 9 квітня 2014 року цю різницю було скасовано, у тому числі ретроспективно по відношенню до тих підпроектів, що на той час вже були завершені або призупинені.
29 червня 2014 року розпочато ESP Sieve в підпроекті PSP Sieve, перейменований на Sierpinski (ESP/PSP/SoB) Sieve, досягнення за яким використовуються для бейджа PSP Sieve.
18 липня 2014 року із PRPNet в BOINC перенесено підпроект PPS-Mega, досягнення за яким зараховуються для бейджа PPS LLR.
20 вересня 2016 року розпочато підпроект AP27 Search, досягнення за яким зараховуються для бейджа AP.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ а б перевіряються проектом Seventeen or Bust
- ↑ Chris Caldwell, The Largest Known Primes