PrimeGrid

PrimeGrid — проект добровольных распределенных вычислений на платформе BOINC, целью которого является поиск различных простых чисел специального вида. Проект стартовал 12 июня 2005 года. По состоянию на 25 марта 2012 года в нём приняли участие более 49 000 пользователей (156 565 компьютеров) из 188 стран, в совокупности обеспечивая производительность 3,3 петафлопс^[1].

Список подпроектов

В проекте производится поиск простых чисел специального вида следующих типов:

• 321-числа: простые числа вида $3 \cdot 2^n \pm 1$;
• числа Софи Жермен: такое простое $p$, что $2p+1$ также является простым;
• обобщенные простые числа Ферма: простые числа вида $a^{2^n}+b^{2^n}$ (частный случай, $k^{2^n}+1$);
• факториальные простые числа (англ.): простые вида $n! \pm 1$ (последовательность A088054 в OEIS);
• праймориальные простые числа (англ.): простые числа вида $n\# \pm 1$ (последовательности A014545 и A014545 в OEIS);
• простые числа Прота: простые числа вида $k \cdot 2^n + 1$, $k$ — нечетно, $2^n > k$ (последовательность A080076 в OEIS);
• простые числа Каллена (англ.): простые числа вида $n \cdot 2^n + 1$ (последовательность A005849 в OEIS);
• простые числа Вудалла (англ.): простые числа вида $n \cdot 2^n - 1$ (последовательность A002234 в OEIS);
• обобщенные простые числа Вудалла: простые числа вида $n \cdot k^n - 1$;
• простые числа Виферича (англ.): такие простые $p$, что $2^{p-1}-1$ делится на $p^2$ (последовательность A001220 в OEIS);
• предположительно простые числа (англ.);
• простые числа-близнецы: пара простых чисел, отличающихся на 2 (последовательности A006512 и A001359 в OEIS).

Поиск простых чисел Каллена, Вудалла, Прота и обобщенных простых чисел Ферма эффективно реализуется с использованием вычислительных возможностей современных видеокарт Nvidia (технология CUDA).

Часть вычислительных мощностей проекта используется для решения открытых математических проблем:

• проблемы Ризеля: поиск такого минимального нечётного $k$, что число $k \cdot 2^n - 1$ является составным для всех натуральных $n$;
• проблемы Серпинского: поиск такого минимального нечетного натурального $k$, что число $k \cdot 2^n + 1$ является составным для всех натуральных $n$ (совместно с проектом Seventeen or Bust).

В 2010 году была успешно найдена арифметическая прогрессия из 26 простых чисел (подпроект AP26).

Для тестов простоты используются алгоритмы Люка-Лемера-Ризеля (англ.) и решета (англ.).

История проекта

3 июля 2007 года добавлен подпроект, направленный на поиск простых чисел Каллена/Вудалла^[2]. Уже 8 августа 2007 года было открыто первое новое простое число Вудалла 2013992×2^2013992−1, содержащее 606 279 цифр^[3].

13 октября 2007 года добавлен подпроект, целью которого является решение проблемы Серпинского^[4].

5 декабря 2007 года добавлен подпроект для поиска чисел вида $3 \cdot 2^n - 1$ с использованием программного обеспечения LLR^[5].

29 июня 2008 года подпроект по поиску чисел вида $3 \cdot 2^n - 1$, проверивший диапазон значений n < 5·10⁶, переключен на поиск чисел вида $3 \cdot 2^n + 1$^[6].

26 декабря 2008 года добавлен подпроект, направленный на поиск праймориальных простых чисел^[7].

27 декабря 2008 года добавлен подпроект AP26, целью которого является поиск арифметической прогрессии из 26 простых чисел^[8].

16 августа 2009 года добавлен подпроект, направленный на поиск простых чисел Софи Жермен^[9].

10 ноября 2009 года добавлен подпроект по поиску обобщенных чисел Ферма^[10].

10 декабря 2009 года для подпроекта AP26 добавлен расчетный клиент с поддержкой технологии CUDA^[11].

31 января 2010 года начато сотрудничество с проектом Seventeen or Bust, направленное на решение проблемы Серпинского^[12].

1 декабря 2010 года анонсирован новый расчетный модуль для поиска простых чисел Прота методом решета с поддержкой технологий CUDA и OpenCL^[13].

7 января 2011 года добавлен подпроект для решения проблемы Серпинского/Ризеля по основанию 5^[14].

9 января 2012 года в модуле LLR реализована поддержка векторных расширений системы команд процессора AVX, что обеспечивает 20—50 % прибавку в производительности в зависимости от приложения^[15].

4 февраля 2012 года реализован расчетный модуль genefer для поиска обобщенных чисел Ферма с поддержкой технологии CUDA^[16].

Научные достижения

В результаты выполняемых расчетов был открыт ряд простых чисел специального вида и арифметических прогрессий из простых чисел.

2007 год

• Числа Вудалла:
  • 3752948×2^3752948−1 (1 129 757 цифр) — самое большое известное простое число Вудалла;
  • 2367906×2^2367906−1 (712 818 цифр);
  • 2013992×2^2013992−1 (606 279 цифр).

2008 год

• 321-числа:
  • 3×2^4235414−1 (1 274 988 цифр).
• Числа Прота:
  • 258317×2^5450519[phone] цифр);
  • 265711×2^4858008[phone] цифры);
  • 651×2⁴⁷⁶⁶³²+1 (143 484 цифры);
  • 825×2³⁷³³³¹+1 (112 387 цифр).

2009 год

• Арифметические прогрессии из 25 простых чисел $(0 \le n \le 24)$:
  • 12353443596260323+23793841×23#×n;
  • 46176957093163301+1109121×23#×n;
  • 18162964758258289+3755664×23#×n;
  • 20919497549238289+3155495×23#×n;
  • 2960886048458003+2346233×23#×n.
• Арифметические прогрессии из 24 простых чисел $(0 \le n \le 23)$:
  • 4891686128805269+19453568×23#×n;
  • 4687877159107031+18203167×23#×n;
  • 1948053460212667+17745794×23#×n;
  • 3634080452156039+16981607×23#×n;
  • 10307159737232191+14120563×23#×n;
  • 13678065943093049+13223804×23#×n;
  • 10317962076055027+10241601×23#×n;
  • 7979661543967237+9936237×23#×n;
  • 39421708111691+9740894×23#×n;
  • 5531900872160491+9383796×23#×n;
  • 13432401425380607+9219580×23#×n;
  • 14992521666441877+8832442×23#×n;
  • 167806194923077+4935146×23#×n;
  • 6274259724784693+2522655×23#×n;
  • 7960592659339799+2326495×23#×n;
  • 6872932294461509+2042703×23#×n;
  • 20187352211709911+1799216×23#×n;
  • 2725131905640097+1342336×23#×n;
  • 25545151920212759+1140241×23#×n;
  • 13785500104035967+1004314×23#×n;
  • 19471368812966089+410682×23#×n;
  • 19516186145019209+313705×23#×n;
  • 20909681071069667+234797×23#×n.
• 321-числа:
  • 3×2^5082306[phone] цифр).
• Числа Каллена:
  • 6679881×2^6679881[phone] цифры) — самое большое известное простое число Каллена;
  • 6328548×2^6328548[phone] цифр).
• Числа Прота:
  • 27×2^2218064+1 (667 706 цифр);
  • 659×2⁶¹⁷⁸¹⁵+1 (185 984 цифры);
  • 519×2⁵⁶⁷²³⁵+1 (170 758 цифр);
  • 15×2⁴⁸³⁰⁹⁸+1 (145 429 цифр).
• Обобщенные простые числа Вудалла:
  • 563528×13⁵⁶³⁵²⁸−1 (627 745 цифр).
• Предположительно простые числа:
  • 2^4583176[phone] цифры).
• Другие:
  • 27×2^1902689−1 (572 768 цифр).

2010 год

• Арифметическая прогрессия из 26 простых чисел $(0 \le n \le 25)$:
  • 43142746595714191+23681770×23#×n.
• Арифметические прогрессии из 25 простых чисел $(0 \le n \le 24)$:
  • 18626565939034793+30821486×23#×n;
  • 25300381597038677+28603610×23#×n;
  • 42592855872841649+19093314×23#×n;
  • 24715375237181843+19071018×23#×n;
  • 46428033558097831+12893265×23#×n;
  • 58555890166091939+10416756×23#×n;
  • 49644063847333931+7851809×23#×n.
• 321-числа:
  • 3×2^6090515−1 (1 833 429 цифр).
• Числа Прота:
  • 90527×2^9162167[phone] цифры).
• Факториальные простые числа:
  • 103040!−1 (471 794 цифры);
  • 94550!−1 (429 390 цифр).
• Праймориальные простые числа:
  • 843301#−1 (365 851 цифра) — самое большое известное праймориальное простое число на момент открытия;
  • 392113#+1 (169 966 цифр).
• Проблема Серпинского — Ризеля по основанию 5:
  • 151026×5⁵⁵⁹⁶⁷⁰−1 (391 198 цифр);
  • 3938×5⁵⁵⁸⁰³²−1 (390 052 цифры);
  • 105782×5⁵⁵¹⁷⁶⁶−1 (385 673 цифры);
  • 183916×5⁵¹⁹⁵⁹⁷−1 (363 188 цифр);
  • 53542×5⁵¹⁵¹⁵⁵−1 (360 083 цифры).
• Проблема Ризеля: найдено простое число 191249×2^3417696−1 (1 028 835 цифр), основание 191249 исключено из рассмотрения.

2011 год

• Простые Софи Жермен:
  • 3756801695685×2⁶⁶⁶⁶⁶⁹±1 (200 700 цифр) — самая большая известная пара простых-близнецов.
• Обобщенные простые числа Ферма:
  • 75898⁵²⁴²⁸⁸[phone] цифр);
  • 361658²⁶²¹⁴⁴[phone] цифр);
  • 145310²⁶²¹⁴⁴[phone] цифр);
  • 40734²⁶²¹⁴⁴[phone] цифр).
• Числа Прота:
  • 9×2^2543551+1 (765 687 цифр);
  • 25×2^2141884+1 (644 773 цифры);
  • 4479×2²²⁶⁶¹⁸+1 (68 223 цифры);
  • 3771×2²²¹⁶⁷⁶+1 (66 736 цифр);
  • 7333×2¹³⁸⁵⁶⁰+1 (41 716 цифр).
• Факториальные простые числа:
  • 110059!-1 (507 082 цифр).
• 321-числа:
  • 3×2^7033641[phone] цифр цифр).
• Обобщенные числа Вудалла:
  • 404882×43⁴⁰⁴⁸⁸²-1 (661 368 цифр).
• Проблема Ризеля: в результате нахождения простых чисел
  • 353159×2^4331116-1 (1 303 802 цифр),
  • 141941×2^4299438-1 (1 294 265 цифр),
  • 123547×2^3804809-1 (1 145 367 цифр),
  • 415267×2^3771929-1 (1 135 470 цифр),
  • 65531×2^3629342-1 (1 092 546 цифр),
  • 428639×2^3506452-1 (1 055 553 цифры)

исключены из рассмотрения основания 428639, 415267, 353159, 141941, 123547, 65531. Непроверенными на тот момент оставались ещё 57 оснований.

2012 год

• Числа Прота:
  • 7×2^5775996[phone] цифр)^[17];
  • 9×2^3497442[phone] цифр)^[18];
  • 81×2^3352924[phone] цифры)^[19];
  • 131×2^1494099+1 (449 771 цифра)^[20];
  • 329×2^1246017+1 (375 092 цифры)^[21];
  • 1705×2⁹⁰⁶¹¹⁰+1 (272 770 цифр)^[22];
  • 7905×2³⁵²²⁸¹+1 (106 052 цифры)^[23].
• Обобщенные простые числа Ферма:
  • 475856⁵²⁴²⁸⁸[phone] цифры) — самое большое известное обобщенное простое число Ферма^[24];
  • 341112⁵²⁴²⁸⁸[phone] цифры)^[25];
  • 773620²⁶²¹⁴⁴[phone] цифры)^[26]
  • 676754²⁶²¹⁴⁴[phone] цифр)^[27]
  • 525094²⁶²¹⁴⁴[phone] цифр)^[28].
• Обобщенные простые числа Каллена:
  • 427194×113⁴²⁷¹⁹⁴+1 (877 069 цифр) — самое большое известное обобщенное простое число Каллена^[29].
• Праймориальные простые числа:
  • 1098133#−1 (476 311 цифр) — самое большое праймориальное простое число среди известных^[30].
• Проблема Ризеля: в результате нахождения простых чисел
  • 252191×2^5497878−1 (1 655 032 цифры)^[31] — наибольшее известное число Ризеля,
  • 162941×2⁹⁹³⁷¹⁸-1 (299 145 цифр)^[32]

исключены из рассмотрения основания 162941 и 252191. Непроверенными остаются ещё 55 оснований.

• Проблема Серпинского: в результате нахождения простых чисел
  • 147559×2^2562218+1 (771 310 цифр),
  • 123287×2^2538167+1 (764 070 цифр)

исключены из рассмотрения основания 123287 и 147559. Непроверенными остаются ещё 15 оснований^[33].

• Простые Софи Жермен:
  • 18543637900515×2⁶⁶⁶⁶⁶⁷−1 (200 701 цифра) — самое большое известное простое Софи Жермен^[34].
• Другие:
  • 27×2^3855094−1 (1 160 501 цифра)^[35].

Примечания

1. ↑ Boinc all Project Stats
2. ↑ New subproject added
3. ↑ Biggest ever Woodall prime discovered!
4. ↑ Prime Sierpinski Project sieve available
5. ↑ New subproject available
6. ↑ 3*2^n-1 switched to +1
7. ↑ Primorial Prime Search
8. ↑ AP26 Search
9. ↑ Sophie Germain Prime Search
10. ↑ Generalized Fermat Prime Search
11. ↑ AP26 CUDA Application Released
12. ↑ Seventeen or Bust
13. ↑ Official release of tpsieve for PPS (Sieve)
14. ↑ Sierpinski/Riesel Base 5 Project
15. ↑ AVX build of llr
16. ↑ Generalized Fermat Prime Search
17. ↑ PPS Mega Prime!
18. ↑ PPS Mega Prime!
19. ↑ Mega Prime Found
20. ↑ Prime Fermat Divisor Found
21. ↑ Prime Fermat Divisor Found
22. ↑ Prime Fermat Divisor Found
23. ↑ Prime Fermat Divisor Found
24. ↑ World Record GFN Prime!
25. ↑ World Record GFN Prime!
26. ↑ Generalized Fermat Mega Prime
27. ↑ Generalized Fermat Mega Prime
28. ↑ Generalized Fermat Mega Prime
29. ↑ World Record Generalized Cullen Prime
30. ↑ World Record Primorial prime
31. ↑ World Record TRP Prime!
32. ↑ Prime found for the Riesel Problem
33. ↑ March was a great month for the Extended Sierpinski Problem project
34. ↑ World Record Sophie Germain prime found!
35. ↑ 27 Mega Prime

Ссылки

• Официальный сайт проекта
• http://primes.utm.edu/largest.html

Обсуждение проекта в форумах:

• boinc.ru
• distributed.ru
• distributed.org.ua

См. также

• Арифметические прогрессии из простых чисел
• Добровольные вычисления
• Открытые проблемы в теории чисел
• Простые числа
• BOINC
• GIMPS
• Seventeen or Bust