Программа для расчета Pi(x)

[ddn]

Где найти программу для расчета (не переборного!) числа простых чисел Pi(x), работающую под Windows XP (!).
Меня интересут весьма любительский, не имеющий теоретического значения, вопрос о номере того или иного большого простого числа либо простого числа с данным номером. Например,

числа Мерсена: pi(M(2))=2, pi(M(3))=4, pi(M(5))=11, pi(M(7))=31, pi(M(13))=1028, реально расчитать pi(M(n)) для n=13, 17, 19, 31, 61, 89, 107, 127 (особый интерес M(31) - 10 знаков и M(127) - 39 знаков). Следующее n=521 слишком велико.

последовательность: c(0)=0; c(n+1)=p(c(n)), что дает для 0<=n<=13 ряд
0, 1, 2, 3, 5, 11, 31, 127, 709, 5381, 52711, 648391, 9737333, 174440041 ...
хотелось бы продолжить.

Для поиска простого числа с данным номером алгоритм такой. Сначала, с помощью точных оценок определяется интервал p(n), потом берется наиболее правдоподобное число k из него и рассчитывается pi(k) - номер первого простого m>=k, затем, либо делается новая приценка k', либо перебераются все числа от k в нужном направлении, проверяя числа на простоту и сдвигая счетчик номера на +-1 за каждое простое.

[maxal]

ddn писал(а):

Где найти программу для расчета (не переборного!) числа простых чисел Pi(x), работающую под Windows XP (!).

В любом мат.пакете такая функция есть. Из бесплатных могу порекомендовать PARI/GP.
Хотя существуют и специальные программы для вычисления $\pi().$

ddn писал(а):

Меня интересут весьма любительский, не имеющий теоретического значения, вопрос о номере того или иного большого простого числа либо простого числа с данным номером. Например,

числа Мерсена: pi(M(2))=2, pi(M(3))=4, pi(M(5))=11, pi(M(7))=31, pi(M(13))=1028, реально расчитать pi(M(n)) для n=13, 17, 19, 31, 61, 89, 107, 127 (особый интерес M(31) - 10 знаков и M(127) - 39 знаков). Следующее n=521 слишком велико.

См. последовательность A059305 - там вычислены значения $\pi(M_p)$ вплоть до $p=31.$
А вот вычислить $\pi(M_{127})$ пока не удастся. На данный момент в вычислениях $\pi()$ подбираются лишь к $10^{23}.$

ddn писал(а):

последовательность: c(0)=0; c(n+1)=p(c(n)), что дает для 0<=n<=13 ряд
0, 1, 2, 3, 5, 11, 31, 127, 709, 5381, 52711, 648391, 9737333, 174440041 ...
хотелось бы продолжить.

См. последовательность A007097.

[ddn]

Спасибо, maxal.
Воспользовавшись таблицей $\pi(n)$ для n с двумя главными разрядами точности, я на Maple сам вычислил $\pi(M_{17})$, $\pi(M_{19})$ и $\pi(M_{31})$ (на последний: 2 часа). И почему в A059305 не смогли найти $\pi(..)$ для $M_{61}$ c какими-то 18 знаками, если подбираются уже к $10^{23}$?
Со статистической точки зрения, вероятность $\pi(M_n)$ быть простым числом ~1/n. Пока это верно для n = 2, 5, 7 и 17, дающие $\pi(M_n)$ = 2, 11, 31 и 12251 - и по идее больше не должно встречаться, не верю я, что номер простого числа имеет теоретико-числовой смысл!

Воспользовавшись той же таблицей, я нашел следующие числа в последовательности из A007097: 3657500101 (1.8 часа) и 88362852307 (16 часа), а прочитал Ваше сообщение - понял, что зря возился.

PARI/GP у меня была, но потом я ее удалил. Убей меня - не понимаю, как пользоваться такими программами. Непостижимый интерфейс.

З. Ы. Тема была перенесена из раздела Математика и я только сейчас, случайно, обнаружил, что по теме уже есть один ответ, когда в нее зашел. В разделе Математика отображается, что число ответов = 0, я и не заглядывал, модератору лучше в таких случаях сообщать о переносе темы и так, чтобы было отмечено число ответов > 0.

[maxal]

ddn писал(а):

И почему в A059305 не смогли найти $\pi(..)$ для $M_{61}$ c какими-то 18 знаками, если подбираются уже к $10^{23}$?

Скорее всего никто серьезно не задавался целью вычислить $\pi(M_{61})$. Надо попробовать скормить $M_{61}$ функции PrimePi[] пакета Mathematica - насколько мне известно, только в нем (из доступных мат.пакетов) для вычисления $\pi()$ реализован алгоритм товарищей Meissel, Lehmer, Lagarias, Miller, Odlyzko, Deléglise и Rivat, гораздо более оптимальный чем обычное просеивание и последующий подсчет простых чисел.

ddn писал(а):

Со статистической точки зрения, вероятность $\pi(M_n)$ быть простым числом ~1/n. Пока это верно для n = 2, 5, 7 и 17, дающие $\pi(M_n)$ = 2, 11, 31 и 12251 - и по идее больше не должно встречаться, не верю я, что номер простого числа имеет теоретико-числовой смысл!

Так вам для этого значения $\pi(M_n)$ понадобились? Я тоже думаю, что других простых чисел вида $\pi(M_n),$ где $M_n$ - простое число Мерсенна, нет. Ну или по крайней мере их конечное число.

ddn писал(а):

PARI/GP у меня была, но потом я ее удалил. Убей меня - не понимаю, как пользоваться такими программами. Непостижимый интерфейс.

Интерфейс вполне нормальный, сложности поначалу возникают с языком - в PARI/GP он несколько своеобразный, что впрочем не уменьшает его функциональности. Поэтому знакомство с PARI/GP я рекомендую начать с чтения документации.

ddn писал(а):

З. Ы. Тема была перенесена из раздела Математика и я только сейчас, случайно, обнаружил, что по теме уже есть один ответ, когда в нее зашел. В разделе Математика отображается, что число ответов = 0, я и не заглядывал, модератору лучше в таких случаях сообщать о переносе темы и так, чтобы было отмечено число ответов > 0.

Пожалуйтесь сюда: http://dxdy.ru/viewforum.php?f=9

Добавлено спустя 2 часа 39 минут 54 секунды:

maxal писал(а):

Надо попробовать скормить $M_{61}$ функции PrimePi[] пакета Mathematica

Не смогла:
PrimePi::largp: Argument 2305843009213693951 in PrimePi[2305843009213693951] is too large for this implementation.

[maxal]

Согласно этим таблицам, $\pi(M_{61}) = 55890484045084135$.