PrimeGrid
![]() | |
Тип | добровільні обчислення і проєкт BOINCd |
---|---|
Автор | 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 — проєкт добровільних розподілених обчислень на платформі BOINC і PRPNet, метою якого є пошук простих чисел різного виду. Проєкт стартував 12 червня 2005 року.
Основна мета проєкту — нести задоволення пересічному користувачу від знаходження простих чисел. Другою метою PrimeGrid є надання відповідних навчальних матеріалів про прості числа.
І нарешті, прості числа грають центральну роль в криптографічних систем, які використовуються для комп'ютерної безпеки. Через вивчення простих чисел можна показати, скільки вимагається обчислень, щоб зламати код шифрування і таким чином визначити, чи є поточні схеми безпеки достатньо безпечними.
Участь у проєкті PrimeGrid можлива у два способи: через BOINC і через Project Staging Area (PSA)
Історія проєкту
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. Завдання GFN-15 стали виключно GPU-сумісні.
2019 рік
- У лютому 2019 року розпочато підпроєкт Do You Feel Lucky?.
- 1 травня 2019 року завершено підпроєкт GCW (Sieve).
- У травні 2019 року усі LLR додатки отримали підтримку AVX-512.
- 6 вересня 2019 року розпочато підпроєкт Fermat Divisor Search.
2020 рік
- 1 лютого 2020 року зупинено видачу завдань GFN-16 для CPU. Завдання GFN-16 стали виключно GPU-сумісні.
- 4 листопада 2020 року завершено підпроєкт 321 Sieve.
- У листопаді 2020 року розпочато підпроєкт Wieferich and Wall-Sun-Sun Prime Search.
2021 рік
- У березні 2021 року завершено підпроєкт 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
- 05.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 35816·52945294−1
- 09.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 146264·52953282−1
- 12.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 238694·52979422−1
- 16.03.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 207494·53017502−1
- 01.05.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 118568·53112069+1
- 13.08.2020 — в PrimeGrid знайдено найбільше відоме просте за основою 5: 109838·53168862−1
Підпроєкти (BOINC)
- 321 Prime Search (LLR)
- Cullen Prime Search (LLR)
- Extended Sierpinski Problem (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)
- 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
- Wieferich and Wall-Sun-Sun Prime 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
- 321 Prime Search Sieve
- Fermat Divisor Search (LLR)
Застосунки
Переваги застосунків
- виконання завдань 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 прості, утворюють послідовність A002253:
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, 16408818.
Експоненти n, для яких відповідні числа форми 3·2n−1 прості, утворюють послідовність A002235:
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, 16819291.
Про 321 Search
Проєкт 321 Search було розпочато у лютому 2003 із листа від Paul Underwood, що шукав допомогу зацікавлених у пошуку простих виду 3·2n−1. Початкова мета була перевірити результати роботи вже проведені проєктом Proth Search і розширити перелік простих до експоненти в 1 мільйон (n=1M). Ця мета була швидко досягнута, тому вони розвинули мету з пошуку мега великих простих, для яких вони провели відсів аж до n=5M.
Результати підпроєкту
Прості числа виду 3·2n±1, що було знайдено у PrimeGrid (станом на 20 січня 2021 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
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 |
3·216408818+1 | 4 939 547 | 25.11.2020 | Scott Brown |
3·216819291−1 | 5 063 112 | 20.01.2021 | Rudi Tapper |
Cullen Prime Search
Cullen Prime Search — це підпроєкт з пошуку простих чисел Каллена. В теорії чисел число Каллена — натуральне число виду Cn = n·2n+1
Експоненти n, для яких відповідні числа Каллена прості, утворюють послідовність A005849:
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.
Станом на грудень 2019 року пошук залишається для 9-ти k, до яких досі не знайдено простих:
91549, 131179, 163187, 200749, 202705, 209611, 227723, 229673, 238411
Результати підпроєкту
Прості, що було знайдено у PrimeGrid (станом на 24 грудня 2019 року):
Прості підпроєкту 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 |
99739·214019102+1 | 4 220 176 | 24.12.2019 | Brian D. Niegocki |
Fermat Divisor Search
Підпроєкт з пошуку простих чисел Прота k·2n+1 — дільників чисел Ферма.
Роботу було розпочато з пошуку простих для k=19683 аж до n=4M.
У другій стадії відбувався пошук для 5<=k<=49 аж до n=9M.
Підпроєкт вважається частиною проєкту Proth Prime Search, отож всі результати і досягнення зараховуються до PPS-LLR.
У березні 2021 року підпроєкт Fermat Divisor Search було завершено.
Результати підпроєкту
Просте число | Цифр | Ділить | Дата | Автор |
---|---|---|---|---|
13·25523860+1 | 1 662 849 | F(5523858) | 22.01.2020 | Scott Brown |
39·26648997+1 | 2 001 550 | 20.10.2020 | Tom Greer | |
39·26684941+1 | 2 012 370 | 20.10.2020 | Mike Thümmler | |
19·26833086+1 | 2 056 966 | 24.10.2020 | Jiri Jaros | |
15·27300254+1 | 2 197 597 | 25.10.2020 | Robert Gelhar | |
29·27374577+1 | 2 219 971 | 27.10.2020 | Pavel Atnashev | |
45·27513661+1 | 2 261 839 | 12.11.2020 | Hiroyuki Okazaki | |
15·27619838+1 | 2 293 801 | 06.12.2020 | anonymous user of China | |
45·27661004+1 | 2 306 194 | 13.12.2020 | Tim Terry | |
29·27899985+1 | 2 378 134 | 14.01.2021 | Tom Greer | |
39·27946769+1 | 2 392 218 | 14.01.2021 | Scott Brown | |
27·27963247+1 | 2 397 178 | F(7963245) | 14.01.2021 | Tom Greer |
31·28348000+1 | 2 513 000 | 19.01.2021 | Igor Karpenko | |
39·28413422+1 | 2 532 694 | 23.01.2021 | Philipp Bliedung | |
25·28456828+1 | 2 545 761 | 27.01.2021 | Wolfgang Schwieger | |
17·28636199+1 | 2 599 757 | 17.02.2021 | Tom Greer | |
25·28788628+1 | 2 645 643 | 01.03.2021 | Tom Greer |
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 не є простим.
Послідовність A076336 відомих чисел Серпінського починається так:
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, окрім наступних 30 значень (станом на 1 травня 2020 року): 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, 126134, 139196, 152588.
Числа Різеля за основою 5
Гіпотеза полягає у тому, що найменшим парним числом Різеля за основою 5 є k=346802. Щоб довести це, достатньо показати, що існує просте число виду k·5n−1 для кожного парного k < 346802. Наразі це доведено для всіх парних k, окрім наступних 62 значень (станом на 13 серпня 2020 року): k = 3622, 4906, 23906, 26222, 35248, 52922, 63838, 64598, 68132, 71146, 76354, 81134, 92936, 102818, 102952, 109238, 109862, 127174, 131848, 134266, 136804, 143632, 145462, 145484, 146756, 147844, 151042, 152428, 154844, 159388, 164852, 170386, 170908, 177742, 182398, 187916, 189766, 190334, 195872, 201778, 204394, 206894, 213988, 231674, 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 |
35816·52945294−1 | 2 058 677 | 05.03.2020 | Pavel Atnashev |
146264·52953282−1 | 2 064 261 | 09.03.2020 | Wolfgang Schwieger |
238694·52979422−1 | 2 082 532 | 12.03.2020 | Chris Howell |
207494·53017502−1 | 2 109 149 | 16.03.2020 | Todd Pickering |
118568·53112069+1 | 2 175 248 | 01.05.2020 | Honza Cholt |
109838·53168862−1 | 2 214 945 | 13.08.2020 | Erik Veit |
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. Станом на 7 лютого 2021 року залишається віднайти прості для 47 чисел k:
2293, 23669, 31859, 38473, 46663, 67117, 74699, 81041, 93839, 97139, 107347, 121889, 129007, 143047, 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 |
146561·211280802−1 | 3 395 865 | 16.11.2020 | Pavel Atnashev |
9221·211392194−1 | 3 429 397 | 07.02.2021 | Barry Schnur |
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, для яких відповідні числа Вудала прості, утворюють послідовність A002234:
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 |
Підпроєкти WW
Wieferich Prime Search
Просте p називається простим Віферіха, якщо p2 ділить 2p-1−1. Ці прості названі за ім'ям Артура Віферіха, німецького математика, який у 1909 році довів, що якщо перша частина останньої теореми Ферма не виконується для деякої експоненти p, тоді p задовільняє умові ap-1 = 1 (mod p2) для a=2.
Незважаючи на численні пошуки, донині відомо лише 2 простих числа Віферіха — це 1093 та 3511. Рідкісність таких простих веде до зацікавлення у пошуку «майже» простих Віферіха. Вони визначаються як спеціальні випадки для малих значень |A|.
Класичне означення близькості
Просте число p, що задовільняє рівнянню для малих значень |A|, назагал називається майже простим Віферіха.
Історія пошуку
Пошук простих і майже простих Віферіха триває вже більше 70 років. Ось історія прогресу:
Верхня межа | Автор | Дата |
---|---|---|
16000 | Beeger | 1940 |
50000 | Froberg | unknown |
100000 | Kravitz | 1960 |
200183 | Pearson | 1964 |
500000 | Riesel | 1964 |
30·106 | Froberg | 1968 |
3·109 | Brillhart, Tonascia, and Weinberger | 1971 |
6·109 | Lehmer | 1981 |
61·109 | Clark | 1996 |
4·1012 | Crandall, Dilcher, and Pomerance | 1997 |
46·1012 | Brown and McIntosh | 2001 |
200·1012 | Crump | 2002 |
1.25·1015 | Knauer and Richstein | 2005 |
3·1015 | Carlisle, Crandall, and Rodenkirch | 2006 |
6.7·1015 | Dorais and Klyve | 2011 |
10·1015 | PrimeGrid | 13.01.2012 |
14·1015 | PrimeGrid | 14.04.2012 |
14·1016 | PrimeGrid | 11.08.2014 |
За цей час верхня межа пошуку досягла вже 136·1015. PrimeGrid почав пошук з 3·1015. Причина цього полягає в тому, що Dorais і Klyve дали інше означення майже простого Віферіха. Таким чином вони не шукали майже простих Віферіха за класичним означенням. PrimeGrid не сподівався знайти простих Віферіха у проміжку між 3·1015 та 6.7·1015, але сподівався знайти декілька майже простих. Так сталося, що визначення майже простого Віферіха, що дали Dorais та Klyve зловило декілька «класичних» майже простих Віферіха, але не всі. PrimeGrid шукає майже прості за умовою |A| < = 1000.
Wall-Sun-Sun Prime Search
Просте Вола-Суня-Суня (або Фібоначчі-Віферіха) — це таке просте p > 5, для якого p2 ділить число Фібоначчі , де символ Лежандра визначається як
Хоча існує гіпотеза, що таких простих існує нескінчено багато, досі не відомо жодного Вола-Суня-Суня простого. Станом на листопад 2013, якщо вони і існують, вони мають бути більші за 26·1015.
Брак удачі в пошуку простих веде до зацікавленості в пошуку «майже» простих Вола-Суня-Суня. Вони визначаються як спеціальні випадки для малих значень |A|.
Класичне означення близькості
Просте число p, що задовільняє рівнянню для малих значень |A|, назагал називається майже простим Вола-Суня-Суня.
Історія пошуку
Вехня межа | Автор | Дата |
---|---|---|
109 | Williams | 1982 |
232 | Montgomery | 1991 |
100·1012 | Knauer and McIntosh | 2003 |
200·1012 | McIntosh and Roettger | 2005 |
970·1012 | Dorais and Klyve | 2011 |
1015 | PrimeGrid | 28.12.2011 |
1.5·1015 | PrimeGrid | 10.01.2012 |
2·1015 | PrimeGrid | 22.01.2012 |
2.5·1015 | PrimeGrid | 02.03.2012 |
6·1015 | PrimeGrid | 29.07.2012 |
28·1015 | PrimeGrid | 31.03.2014 |
Числа названі на честь Доналда Дайнса Вола (Donald Dines Wall) і братів близнюків Чжи Хон Суня (Zhi Hong Sun) та Чжи Вей Суня (Zhi Wei Sun), які в 1992 році показали, що якщо перша умова великої теореми Ферма не виконується для певного простого p, то p має бути простим числом Фібоначчі — Віферіха. Таким чином, до того, як велика теорема Ферма була доведена Ендрю Вайлсом, пошук простих Фібоначчі — Віферіха переслідував мету знайти потенційний контрприклад.
PrimeGrid шукає майже прості за умовою |A| < = 1000.
Підпроєкти 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 (станом на 21 січня 2020 року):
Просте число | Цифр | Дата | Автор |
---|---|---|---|
10590941048576+1 | 6 317 602 | 31.10.2018 | Rob Gahan |
9194441048576+1 | 6 253 210 | 29.08.2017 | Sylvanus A. Zimmerman |
3638450524288+1 | 3 439 810 | 29.05.2020 | Wolfgang Schwieger |
3214654524288+1 | 3 411 613 | 24.12.2019 | Alen Kecic |
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 |
9812766262144+1 | 1 832 857 | 16.02.2020 | Tom Greer |
9750938262144+1 | 1 832 137 | 12.02.2020 | Alen Kecic |
9450844262144+1 | 1 828 578 | 21.01.2020 | Jacob Eikelenboom |
9125820262144+1 | 1 824 594 | 05.12.2019 | Yoshimitsu Kato |
8883864262144+1 | 1 821 535 | 09.09.2019 | Rod Skinner |
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 | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
WW |
До квітня 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