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

[ArtemKim]

Спасибо, Rip. Вы очень помогли.

[AndAll]

Думаю, ближе всего к Вашему вопросу идеи изложенные здесь:
The Liu Fengsui's Prime Formula http://www.primepuzzles.net/problems/prob_037.htm

[math_x8]

следующее простое число больше заданного:
http://ru.numberempire.com/primenumbers.php

[маткиб]

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

Sonic86 писал(а):

Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.

Было бы любопытно посмотреть на доказательство.

Присоединяюсь к вопросу про доказательство. Я, например, точно знаю, что если разрешить округление, деление, вычитание, модуль, то такая формула существует, даже если использовать только целочисленные константы. Вообще говоря, операция возведения в степень даёт очень много возможностей и очень сильно портит в плане доказательства таких вот "нижних оценок".

[hurtsy]

Цитата:

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

Sonic86 писал(а):
Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.


Было бы любопытно посмотреть на доказательство.

-----------------------------------------------------------------------------------------------------
Существуют доказательства в учебниках по теории чисел, что полином от целочисленной переменной n-степени с целочисленными коэфициентами не может принимать более чем n простых значений. См. например Бухштаб А.А. Теория чисел. – 2-е изд. – М.: Просвещение, 1966. –С. 384 или любой другой учебник по теории чисел.С уважением,

[маткиб]

а если переменная в показателе?

[hurtsy]

Цитата:

маткиб Добавлено: Вт Июл 01, 2008 16:41:56 Заголовок сообщения:

--------------------------------------------------------------------------------

а если переменная в показателе?

Экспонента, конечно, страшная сила. Но боюсь ничего это не даст. По моему мнению существо достаточно больших простых чисел становится чисто вероятностным, как противоположность детерминированности натурального ряда. Это следует из процесса известного под названием "решето Ератосфена" . С уважением,

[naiv1]

hurtsy писал(а):

По моему мнению существо достаточно больших простых чисел становится чисто вероятностным,

Что имеете в виду?

hurtsy писал(а):

...как противоположность детерминированности натурального ряда.

В каком смысле?

hurtsy писал(а):

Это следует из процесса известного под названием "решето Ератосфена"

Каким образом? Можно разъяснить по-подробнее?

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

Из теоремы Матиясевича следует, что существуют многочлены $f(x_1, \ldots, x_k, y)$ и $g(x_1, \ldots, x_n, y)$ с целыми коэффициентами, такие что для любого $y \in \mathbb{N}$

1) $(\exists x_1, \ldots, x_k \in \mathbb{N})(f(x_1,\ldots,x_k,y)=0)$ тогда и только тогда, когда число $y$ --- простое;

2) $(\exists x_1, \ldots, x_n \in \mathbb{N})(g(x_1,\ldots,x_n,y)=0)$ тогда и только тогда, когда число $y$ --- составное.

Здесь даже возведение в степень не используется --- только сложение и умножение (ну и ещё, строго говоря, вычитание, коэффициенты ведь могут быть отрицательны). Правда, нельзя сказать, что функции $f$ и $g$ "перечисляют" простые и составные числа. Они "выделяют" их несколько по другому.

Но из них, конечно, можно легко получить и "перечисляющие" функции. К примеру рассмотрим функцию

$$ h(x_1, \ldots, x_k,y) = y \cdot (1 - \mathrm{sg}(f(x_1, \ldots, x_k,y))) + 2 \cdot \mathrm{sg}(f(x_1, \ldots, x_k,y)), $$

где $\mathrm{sg}$ --- функция из $\mathbb{N}$ в $\mathbb{N}$, такая что

$$ \mathrm{sg}(n) = \begin{cases} 0, &n=0 \\ 1, &n>0 \end{cases} $$

Ясно, что подставляя в $h$ натуральные числа вместо аргументов, мы будем получать в качестве значений все простые числа.

Надо подумать насчёт того, можно ли обойтись без сигнума

P. S. $\mathbb{N} = \{ 0,1,2,\ldots \}$

[Sonic86]

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

Цитата:

Было бы любопытно посмотреть на доказательство

Немного не уверен (чисто умозрительно, ... не критикуйте сильно.)...
Смысл такой, что если $p_n$ - какая-то последовательность простых чисел (необязательно всех),
то для любого простого $q$, лежащего в этой последовательности $p_n \mod q$ - непериодическая функция,
в то время как для любой функции $F(n)$, построенной из сложения, умножения, возведения в степень
и принимающей натуральные значения, функция $F(n) \mod q$ будет периодической
(для многочленов это очевидно, а в общем - надо доказывать по индукции. Это смысл доказательства, его можно критиковать, но бессмысленно - он - для понимания).
Поэтому невозможно чтобы $(\forall n) F(n)=p_n $

С формальным доказательством у меня похуже.

0. Обозначим $a \mod b$ остаток от деления $a$ на $b \in \mathbb(N)$.

1. Пусть $n \in \mathbb N$. Обозначим $S(x,y)=x+y, M(x,y)=xy, D(x,y)=x^y$.
Определим Р-функции от $n$:
$E(n)=n$ - Р-функция.
Если $x,y \in \mathbb Z$ или $x,y$ - Р-функции от $n$, и для любого $n$
$S(x,y), M(x,y), D(x,y)$ - определены и принимают натуральные значения (это далее - по умолчанию),
то $S(x,y); M(x,y), D(x,y)$ - тоже Р-функции от $n$.

2. Пусть $F(n)$ - такая функция: $F(n)$ - простое. Пусть для произвольного $a$ $F(а) = q$ - простое.
Тогда $F(n) \mod q$ - непериодическая функция, либо $F(n)$ принимает конечное число значений.
Интуитивно, $F(a) \mod q = q \modq = 0$, а для большого числа значений $b$ $F(b) \mod q = \neq 0$,
поэтому $F(n) \mod q$ - действительно непериодическая.

3. Если $F(n)$ - Р-функция, то $F(n) \mod q$ периодическая функция для любого $q$. Докажем по индукции.
$E(n)=n$ - Р-функция, $E(n) \mod q$ - периодическая.
Пусть $x,y \in \mathbb Z$ или $x,y$ - Р-функции от $n$.
Тогда по предположению $x \mod q, y \mod q$ - периодические функции, периоды: $T_1 , T_2 \in \mathbb N$
Тогда $S(x,y), M(x,y)$ - тоже Р-функции, а $S(x,y) \mod q, M(x,y) \mod q$ - периодические с периодом $lcm(T_1 , T_2)$
(так как $(x+y) \mod q=(x \mod q+y \mod q) \mod q$ и $(xy) \mod q=(x \mod q y \mod q) \mod q$)

Кроме того, $D(x,y)$ - тоже Р-функция, а период $D(x,y) \mod q$ будет равен $lcm(T_1 , \varphi (T_3 ))$,
где $\varphi$ - функция Эйлера (так как $(x^y) \mod q=(xmodq)^{y \mod (\varphi(q))} \mod q$).
В данном случае $T_3$ - период функции $y \mod (\varphi(q))$ (простота $q$ не требуется).
То есть $D(x,y)modq$ - тоже периодическая функция.

Таким образом, для любой Р-функции $F(n)$,
соответствующая ей функция $F(n) \mod q$ - периодическая для любого $q$.

4. Пусть $F(n)$ - Р-функция, принимающая только простые значения (в неограниченном количестве),
а $F(n) \mod q$ - соответствующая ей функция, где $q \in E(F)$
Согласно 2 $F(n) \mod q$ непериодическая, согласно 3 $F(n) \mod q$ периодическая.
Следовательно, $F(n)$ не существует.

Замечания:
1. (функции, принимающие ненатуральные значения, я не рассматриваю хотя бы ради простоты.)
В каждом конкретном случае надо проверять, является ли выражение Р-функцией.
В нужных случаях это обычно легко. Жалко модуля функции нету.
Можно было бы рассматривать целочисленные значения.

2. Это утверждение даже - тавтология, просто по отношению к этой функции:
функция либо периодична, либо непериодична. Если она периодична и принимает
только натуральные значения, то она принимает конечное число значений. Функции,
принимающие конечное число значений нас не интересуют. Значит, считаем нашу функцию
непериодичной (я этот момент только при изложении заметил. Формально - правильно,
но тогда доказательство для меня теряет смысл! Тут импликация и интуиция не сходятся)
Вот, к примеру $p_n \mod 5 = 2,3,0,2,1,3,2,4,3,4,1,2,1,3,2,3,4,1,2,1,3,4,3,4,2,...$
- интуитивно очевидно, что эта последовательность случайна.

3. Вот, например $(2^n-n^2) \mod 5 =1,0,4,0,2,3,...$. Период $2^n$ равно 4, $n^2$ - 5,
значит, общий период - 20. В этом можно непосредственно убедиться.

Доказательство можно усложнить, если к Р-функциям еще добавить функции:
Если $F(n)$ - Р-функция и $D=gcd \limits{n} (F(n))$, то $F(n)/D$ - Р-функция.

У меня у самого вопрос: как доказывается, что для такого-то $k$ все числа Серпинского $k2^n +1$
являются составными? Хотя бы так: через делимость чисел и разложения формулы на множители
или как-то сложнее? Подскажите, очень интересно.

З.Ы. Еще более "тупое" доказательство, что нет такой формулы, выдающей все простые:
$p_n \equiv nln(n)$, а $F(n) \equiv an^m$, либо растет еще быстрее.
(не знаю как асимптотические символы писать)

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

Sonic86 писал(а):

Смысл такой, что если $p_n$ - какая-то последовательность простых чисел (необязательно всех), то для любого простого $q$, лежащего в этой последовательности $p_n mod q$ - непериодическая функция...

А что Вы понимаете под $p_n \mod q$? Остаток от деления $p_n$ на $q$ или что-то другое? Если остаток, то утверждение явно не верно: возьмите, например, $q=2$.

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

Дальше ещё веселее.

Sonic86 писал(а):

Тогда $F(n)modq$ - непериодическая функция, либо принимает конечное число значений.

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

[Someone]

Извините за offtopic, но формулы выглядят ужасно.

Sonic86 писал(а):

$b \in \mathbb(N)$

Sonic86 писал(а):

$(xy)modq=(xmodq ymodq)modq$

Должно быть так:

$b\in\mathbb N$

$(xy)\mod q=(x\mod q)(y\mod q)\mod q$

$b\in\mathbb N$

$(xy)\mod q=(x\mod q)(y\mod q)\mod q$

[hurtsy]

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

Из теоремы Матиясевича следует, что существуют многочлены $f(x_1, \ldots, x_k, y)$ и $g(x_1, \ldots, x_n, y)$ с целыми коэффициентами, такие что для любого $y \in \mathbb{N}$

1) $(\exists x_1, \ldots, x_k \in \mathbb{N})(f(x_1,\ldots,x_k,y)=0)$ тогда и только тогда, когда число $y$ --- простое;

2) $(\exists x_1, \ldots, x_n \in \mathbb{N})(g(x_1,\ldots,x_n,y)=0)$ тогда и только тогда, когда число $y$ --- составное.


Но из них, конечно, можно легко получить и "перечисляющие" функции. К примеру рассмотрим функцию

$$ h(x_1, \ldots, x_k,y) = y \cdot (1 - \mathrm{sg}(f(x_1, \ldots, x_k,y))) + 2 \cdot \mathrm{sg}(f(x_1, \ldots, x_k,y)), $$

где $\mathrm{sg}$ --- функция из $\mathbb{N}$ в $\mathbb{N}$, такая что

$$ \mathrm{sg}(n) = \begin{cases} 0, &n=0 \\ 1, &n>0 \end{cases} $$

1. Лучше привести формулировку теоремы, чем ссылку на жизнеописание.
2. Что такое многочлен с бесконечным количеством нулей?
3. Зачем введен $g(x_1, \ldots, x_n, y)$, если он не используется в выкладках.
С уважением,

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

naiv1 писал(а):

hurtsy писал(а):

По моему мнению существо достаточно больших простых чисел становится чисто вероятностным,

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

hurtsy писал(а):

...как противоположность детерминированности натурального ряда.

В каком смысле?
В том смысле, что если есть натуральное n то можно считать n+1 натуральным числом.

hurtsy писал(а):

Это следует из процесса известного под названием "решето Ератосфена"

Каким образом? Можно разъяснить по-подробнее?
Если Вы определите необходимую и достаточную степень подробности, я попытаюсь. С уважением,

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

hurtsy писал(а):

Лучше привести формулировку теоремы, чем ссылку на жизнеописание.

Пожалуйста!

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

hurtsy писал(а):

Что такое многочлен с бесконечным количеством нулей?

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

hurtsy писал(а):

Зачем введен $g(x_1,\ldots,x_n,y)$, если он не используется в выкладках?

Чтобы кто-нибудь об этом спросил

[ddn]

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

Из теоремы Матиясевича следует, что существуют многочлены $f(x_1, \ldots, x_k, y)$ и $g(x_1, \ldots, x_n, y)$ с целыми коэффициентами, такие что для любого $y \in \mathbb{N}$

1) $(\exists x_1, \ldots, x_k \in \mathbb{N})(f(x_1,\ldots,x_k,y)=0)$ тогда и только тогда, когда число $y$ --- простое;

2) $(\exists x_1, \ldots, x_n \in \mathbb{N})(g(x_1,\ldots,x_n,y)=0)$ тогда и только тогда, когда число $y$ --- составное.

Я знаю совсем другую формулировку.
Существуют натуральное $n$ и многочлен $f(\{x_k\}|_{k=1}^n)$ с целыми коэффициентами, что для любых $x_k\in \mathbb{N}$($\mathbb{Z}$?) имеем $f(\{x_k\}|_{k=1}^n)>0$ тогда и только тогда, когда число $f(\{x_k\}|_{k=1}^n)$ простое, и множество неотрицательных значений $f(\{x_k\}|_{k=1}^n)$ пробегает все простые числа.
И Матиясевич построил пример такого многочлена для $n=23$.
Не уверен, что эта формулировка эквивалентна той, предложил Профессор Снэйп.