Определение. Если число 2N−1
простое, то оно называется простым числом Мерсенна.
Например, 22−1 — первое простое число Мерсенна,
23−1 — второе, 211213−1 — 23-e,
2216091−1 — 31-e.
Искать эти числа без компьютера довольно тяжело. Так, Эйлер в 1772 году нашёл 8-е число, 231−1, но после этого в течение 100 лет не было найдено ни одного! Лишь в 1876 Люк показал, что 2127−1 —
простое число. Но он нашел не 9-е, а сразу 12-е, так как 261−1, 289−1, 2107−1 — тоже простые, но были найдены позднее. Новый прорыв случился лишь в 1950-х, когда с помощью вычислительной техники были найдены простые числа Мерсенна с показателями 521, 607, 1279, 2203, 2281. Все последующие числа Мерсенна были найдены с помощью ЭВМ. И для этого не нужно было быть великим математиком, в 1978 и 1979 годах студенты Нолл и Никел нашли 25-е и 26-е числа (21701 и 23209) на мэйнфрейме своего университета, чем и прославились на всю Америку. Но и у современных суперкомпьютеров есть пределы возможностей. Сегодня простые числа Мерсенна ищут десятки тысяч людей по всему миру, объединённые одним метапроектом GIMPS (Great Internet Mersenne Prime Search, www.mersenne.org). На счету GIMPS уже 8 самых больших простых чисел Мерсенна. Их показатели — 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951. 26972593−1 является 38-м
простым числом Мерсенна, а про последние 4 ещё нельзя сказать, какие они по счету, т.к. ещё не все меньшие числа проверены. Эти же 4 числа являются самыми большими известными простыми числами.
Последнее число — 225964951−1 — было найдено 18 февраля 2005 года, оно состоит из 7816230 десятичных цифр, тот же, кто найдёт простое число более чем из 10 миллионов цифр, получит приз в $100000. Эти деньги можете выиграть и Вы, если присоединитесь к проекту.
Сейчас от Вас, конечно, не требуется найти за 5 часов 43-е простое число Мерсенна, ведь жюри просто не сможет проверить Ваш ответ. В этой задаче N не превосходит 38. Итак, Вам даётся N, от Вас требуется найти N-е по порядку простое число Мерсенна.
(Информация приведена по состоянию на март 2005)
Исходные данные
В первой строке дано число T — количество тестов. В каждой из последующих T строк дано число N.
Результат
Для каждого числа N выведите показатель N-го по порядку простого числа Мерсенна.
Пример
исходные данные | результат |
---|
13
18
32
24
21
19
34
27
33
20
30
28
29
22
| 3217
756839
19937
9689
4253
1257787
44497
859433
4423
132049
86243
110503
9941
|
Автор задачи: Владимир Яковлев
Источник задачи: Чемпионат школьников. Март 2005