Формула для n-ного простого числа

[hurtsy]

Профессор Снэйп писал(а):

Цитата:

Каждое рекурсивно перечислимое отношение задаётся на $\mathbb{N}$ экзистенциальной формулой языка элементарной арифметики.

Спасибо. Если у Вас уже есть рекурсивно-перечислимое отношение для всех простых чисел, то все остальные рассуждения нужны, для того чтобы кто нибудь спросил.

Цитата:

Вас что интересует: определение многочлена или "неожиданный" факт, гласящий, что у ненулевого многочлена от нескольких переменных нулей может быть бесконечно много?

Да. И то и другое "и можно в одну посудину". С уважением,

[Профессор Снэйп]

hurtsy писал(а):

Если у Вас уже есть рекурсивно-перечислимое отношение для всех простых чисел, то все остальные рассуждения нужны...

Да, "уже есть". И не только у меня, а у любого мало-мальски грамотного студента-первокурсника, знакомого с основами теории вычислимости.

hurtsy писал(а):

Да. И то и другое "и можно в одну посудину". С уважением,

1) Многочленом с коэффициентами из коммутативного кольца $A$ и переменными из множества $S$ называется элемент моноидной алгебры $A[\mathbb{N}\langle S \rangle]$.

2) Рассмотрите многочлен $f(x,y) = x-y$. Все пары $\langle x,x \rangle$ для $x \in \mathbb{N}$ будут его корнями, не так ли?

Добавлено спустя 19 минут 42 секунды:

ddn писал(а):

Я знаю совсем другую формулировку...

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

Единственное, что могу сказать: решение 10-ой проблемы Гильберта из этой формулировки действительно следует. А из Вашей --- нет, не вижу, как могло бы следовать. А ведь Матиясевич прославился именно тем, что сделал завершающий шаг в решении 10-ой проблемы Гильберта!

[hurtsy]

Профессору Снэйп.

Большое спасибо. Было весело. Ваши рассуждения понятны. Я считал, что дискусия идет на тему арифметических простых чисел, а многочлены имеются в виду от одной переменной. Но что Вы можете посоветовать если требуется найти штук 10 простых чисел с например 2008 десятичними знаками. С уважением,

[Профессор Снэйп]

hurtsy писал(а):

Я считал, что дискусия идет на тему арифметических простых чисел, а многочлены имеются в виду от одной переменной.

Угу. Если написано $f(x_1, \ldots, x_k,y)$, то $f$ --- многочлен от одной переменной, и никак иначе

С термином "арифметические простые числа" сталкиваюсь первый раз. Они что, бывают "не арифметические"?

[naiv1]

hurtsy писал(а):

Я имею в виду, что проверка простоты больших простых чисел не производится прямым перебором возможных делителей. Используемые методы (probabalistic algorithm вероятностный алгоритм).

Означает ли это, что число, прошедшее успешную проверку на простоту этими вероятностными методами, может быть на самом деле составным?

[Brukvalub]

naiv1 писал(а):

Означает ли это, что число, прошедшее успешную проверку на простоту этими вероятностными методами, может быть на самом деле составным?

Означает. Например, в тесте Миллера — Рабина после получения k проверок и получения k случайных "свидетелей простоты" проверяемого числа выдается ответ, что проверяемое число является простым с вероятностью не менее, чем

\[ 1 - \frac{1}{{2^{2k} }} \]

. И такой ответ всех обычно устраивает
Вот неплохая книга с описанием подобного рода алгоритмов:
Василенко О.Н. — Теоретико-числовые алгоритмы в криптографии

[Sonic86]

Я форму исправил - спасибо за критику формул.
Как насчет содержания?

// обсуждение алгоритма Конвея вынесено в соответствующую тему // maxal

[vovkaturov]

Про полином Матиясевича отсюда: ссылка


Правильно ли я понимаю, что для практического получения
простых чисел этот полином бесполезен?
А вероятность получения положительного значения
путём случайной генерации переменных исчезающе мала?

[Sonic86]

vovkaturov в сообщении #544129 писал(а):

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

Довольно трудно поверить в то, что он полезен.

vovkaturov в сообщении #544129 писал(а):

А вероятность получения положительного значения путём случайной генерации переменных исчезающе мала?

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

[vovkaturov]

Sonic86 писал(а):

Можно попытаться пробежать по единичному кубу хотя бы ради интереса...

В этой формуле из статьи точно нет ошибок? Там же в скобках единица минус одни квадраты, как этот полином вообще может положительные значения принимать?

[nnosipov]

vovkaturov в сообщении #544201 писал(а):

Там же в скобках единица минус одни квадраты, как этот полином вообще может положительные значения принимать?

Может, но только если все квадраты будут нулевыми.

[vovkaturov]

nnosipov писал(а):

Может, но только если все квадраты будут нулевыми.

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

[vicvolf]

vovkaturov в сообщении #544207 писал(а):

nnosipov писал(а):

Может, но только если все квадраты будут нулевыми.

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

Тема начиналась с вопроса-существует ли формула простых чисел. Существует и ни одна http://ega-math.narod.ru/Quant/Primes.htm
Вопрос использования этих формул тоже интересен, но уже другой!

[serega57]

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

vovkaturov в сообщении #544129 писал(а):

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

Довольно трудно поверить в то, что он полезен.

vovkaturov в сообщении #544129 писал(а):

А вероятность получения положительного значения путём случайной генерации переменных исчезающе мала?

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

Если мне память не изменяет то этот многочлен давно сократили то-ли до 12 то-ли до8 знаков. А сам автор пришел к выводу что несушествует не каких формул для простых чисел кроме как сплошного перебора.

[Sonic86]

serega57 в сообщении #544300 писал(а):

Если мне память не изменяет то этот многочлен давно сократили то-ли до 12 то-ли до8 знаков. А сам автор пришел к выводу что несушествует не каких формул для простых чисел кроме как сплошного перебора.

Вообще как бы между формулами и алгоритмами особой разницы нет. Алгоритмов генерации простых и их проверки - множество. Можно посмотреть в том же Василенко.