гипотеза Римана

[Sonic86]

alexo2 в сообщении #664738 писал(а):

Насколько я понял, здесь гарантируется только то, что среди сгенерированных чисел будут обязятельно простые и не более?

Нет, автомат выдает их все по порядку (я только не помню, по номеру, или по предыдущему простому. Кажется, последнее). Можете сами повычислять, муторно, но работает. Асимптотика у алгоритма фиговая, конечно.

[hurtsy]

Sonic86 в сообщении #664537 писал(а):

Например, решето Эратосфена позволяет получить простое число по его номеру.

Извините за непонимание . Просеивание с 2 дает простые в интервале (2,9) - три штуки. Нумеровать простые возможно только после соответствующего просеивания, а не до того. С уважением,

[Someone]

А в чём проблема-то? Просеиваем и отсчитываем столько, сколько нужно.

[itmanager85]

Sonic86 , асимптотический вывод - я имел ввиду
в доказательство $q(n) < H_n + \exp(H_n)\ln{H_n}$ при $n > 1$ .

[hurtsy]

Someone в сообщении #664958 писал(а):

А в чём проблема-то? Просеиваем и отсчитываем столько, сколько нужно.

Проблема в том, что оценка "сколько нужно" должна гарантировать абсолютное отклонение от истинного номера меньше 2, в таком случае не нужно будет ожидать конца отсчитывания . С уважением,

[Someone]

hurtsy в сообщении #665074 писал(а):

оценка "сколько нужно" должна гарантировать абсолютное отклонение от истинного номера меньше 2

Зачем?

$p_1=2$.
Если мало, просеиваем числа, меньшие $(p_1+1)^2=9$, находим $p_2=3$, $p_3=5$, $p_4=7$.
Если мало, просеиваем числа, меньшие $p_3^2=25$, находим $p_5=11$, $p_6=13$, $p_7=17$, $p_8=19$, $p_9=23$.
Если мало, просеиваем числа, меньшие $p_4^2=49$, находим $p_{10}=29$, $p_{11}=31$, $p_{12}=37$, $p_{13}=41$, $p_{14}=43$, $p_{15}=47$.
Если мало, просеиваем числа, меньшие $p_5^2=121$, ...

Никаких априорных оценок для этого алгоритма не требуется. Другое дело, что он, разумеется, очень далёк от оптимальности. Например, на моём компьютере Wolfram Mathematica 5.1 находит $p_{10000000000}=252097800623$ за $1{,}641$ секунды и $p_{100000000000}=2760727302517$ за $8{,}484$ секунды. Ясно, что в этом случае сплошным просеиванием она не занимается. В описании функции $\mathbf{Pime[n]}$ сказано:

Цитата:

Prime and PrimePi use sparse caching and sieving. For large $n$, the Lagarias‐Miller‐Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime.

[hurtsy]

Someone в сообщении #665165 писал(а):

Зачем?

Я на Maple 13

> a := 10^1000;
print(`output redirected...`); # input placeholder
10000000000000000000000000000000000000000000000000000000000000000000000000000\

  00000000000000000000000[...801 digits...]0000000000000000000000000000000000\

  000000000000000000000000000000000000000000000000000000000000000000
> a := nextprime(a);
print(`output redirected...`); # input placeholder
10000000000000000000000000000000000000000000000000000000000000000000000000000\

  00000000000000000000000[...801 digits...]0000000000000000000000000000000000\

  000000000000000000000000000000000000000000000000000000000000004351

Я время не засекал, порядка 10сек. А вот как номер определить? Есть тут функция ithprime(x) но даже для $x=10^{10}$ за минуту не получил результат. С уважением,

[Someone]

(hurtsy)

hurtsy в сообщении #665423 писал(а):

4351

Странно. Я на своей Wolfram Mathematica 5.1 запустил команды
$\mathbf{<< NumberTheory`NumberTheoryFunctions`}$
$\mathbf{a=0;While[a\leq 4351,Print[Timing[p=NextPrime[10^{1000}+a]]];a=p-10^{1000}]}$
и получил следующие значения $a$, для которых число $10^{1000}+a$ простое:
$453$ ($5{,}984$ с);
$1357$ ($10{,}328$ с);
$2713$ ($15{,}391$ с);
$4351$ ($15{,}953$ с);
$5733$ ($14{,}938$ с).
Получается, что Maple три простых числа пропустил.

[Aritaborian]

Someone, оформляйте код как код, а не как ТеХ, читать же невозможно ;-)

[hurtsy]

Someone
Нет, я просто не делал цикла, а оператор выполнил 4 раза. У Maple те же значения. Но ведь значения простых программа гарантирует достоверность, кажется, для 200 знаков. Все таки получение простого числа по заданному номеру вопрос открыт. С уважением,

[Someone]

(Оффтоп)

hurtsy в сообщении #665568 писал(а):

я просто не делал цикла, а оператор выполнил 4 раза

Понятно. Но по тому, что Вы изобразили, догадаться об этом невозможно.

hurtsy в сообщении #665568 писал(а):

Но ведь значения простых программа гарантирует достоверность, кажется, для 200 знаков.

Да, доказательство простоты случайного большого числа - задача достаточно сложная и трудоёмкая. Но есть специальные программы. Например, Primo. Она справляется с числами до 10000 цифр. Правда, времени требует много. Перечисленные мной числа она сертифицирует как простые, тратит при этом от 29 до 38 минут на одно число. Для чисел, близких к верхнему пределу, требуется несколько тысяч часов. Для чисел специального вида есть программа pfgw.

Aritaborian в сообщении #665557 писал(а):

оформляйте код как код, а не как ТеХ, читать же невозможно

Ладно, не преувеличивайте. В таком виде текст более похож на то, что изображает сама Mathematica. Но специально для Вас оформлю как код:

<< NumberTheory`NumberTheoryFunctions`
a=0;While[a<=4351,Print[Timing[p=NextPrime[10^1000+a]]];a=p-10^1000]

[Aritaborian]

Someone

(Оффтоп)

Ничего он не похож. Mathematica использует моноширинный шрифт типа Курьера. Я обычно использую здесь тег tt.