math.luga.ru : Форум

Требуется привести рекурсивно примитивную функцию множеством значений которых является множество простых чисел.
Нашел многочлен с 26 коэффициентами, может кто-нить укажет смысл этих коэффициентов? (http://mindspring.narod.ru/math/ega/Liv/Zagier.htm#ref1)

Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(s)??

Приведу пример такой примитивно рекурсивной функции:
(я расчитываю на то, что вы знакомы с некими начальными понятиями...)
1)sgn'(0)=1, sgn'(N)=0 при N>1; sgn' - примитивно рекурсивна;
2)rest(N,M) - остаток от деления N на M, rest(N,0)=N - примитивно рекурсивная функция;
3)Количество делителей числа N
div(N)=(сумма по i от 0 до N)[sgn'(rest(N,i))]
и количество простых чисел, не превосходящих N,
pp(N)=(сумма по i от 0 до N)[sgn'(|div(N)-2|)]
являются примитивно рекурсивными, как композиции примитивно рекурсивных функций (считаем, что div(0)=0 );
4)Перенумеруем все прoстые числа в проядке возрастания: p_0=2, p_1=3, p_2=5, ... Тогда n-е простое число - это наименьшее число, такое, что pp(N)=n+1, т.е. p_N=(минимизация по y)|pp(y)-(N+1)|.
5) Для примитивной рекурсивности осталось доказать, что решение уравнения |pp(y)-(N+1)|=0 ограничено сверху примитивно рекурсивной функцией от N. Но p_N <= 2^(2^N). Докажем это по индукции. Для N=0 это верно. Переход:
p_N <= p_0*p_1*...*p_(N-1) +1 <=
[2^(2^0)]*[2^(2^1)]*...*[2^(2^(N-1))]+1 <
< 2*2^(1+2+...+2^(N-1))=2^(2^N) .

Вроде всё.

ИМХО необязательно всё так усложнять, нам ведь надо всего лишь функцию, область значений которой - множество простых чисел. можно взять например такую (за П я обозначил произведение: П(диапазон){выражение}):
F(x)=(x-1)*П(1<i<=x){sgn(rest(x+1,i))}+2
которая будет отдавать число х+1 если х+1 простое и 2-ку в противном случае =)
она примитивно рекурсивна как композиция примитивно рекурсивных функций

Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(s)??

f(s)=1-(sin(pi*Г(s)/s))/(sin(pi/s))
утверждается, что все s при которых f(s)=0 являются простыми числами. нетрудно видеть что f(s)=0 только если (sin(pi*Г(s)/s))/(sin(pi/s))=1, ну или sin(pi*Г(s)/s)=sin(pi/s) а это возможно, например, если
pi*Г(s)/s+pi/s=pi ну или Г(s)/s+1/s=1 что всё равно что Г(s)+1=s ну или Г(s)=s-1. нетрудно видеть что подобным свойством обладает знаменитая функция Эйлера, так что, я полагаю, Г(s) это она и есть =)

Влад писал(а):Приведу пример такой примитивно рекурсивной Тогда n-е простое число - это наименьшее число, такое, что pp(N)=n+1, т.е. p_N=(минимизация по y)|pp(y)-(N+1)|.

Спасибо! Я вчера открыл книжку Мальцева А.И (НГУ) на стр. 59 была формула с оператором минимизации. Кажется это и имелось ввиду.
P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?

kaval писал(а):ИМХО необязательно всё так усложнять, нам ведь надо всего лишь функцию, область значений которой - множество простых чисел. можно взять например такую (за П я обозначил произведение: П(диапазон){выражение}):
F(x)=(x-1)*П(1<i<=x){sgn(rest(x+1,i))}+2
которая будет отдавать число х+1 если х+1 простое и 2-ку в противном случае =)
она примитивно рекурсивна как композиция примитивно рекурсивных функций

Сначала подумал, что это похоже на характеристическую функцию множества, потом пригляделся, а там х+1 или 2 в рез-те! Хитро, браво

kaval писал(а):

Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(s)??

f(s)=1-(sin(pi*Г(s)/s))/(sin(pi/s))
утверждается, что все s при которых f(s)=0 являются простыми числами. нетрудно видеть что f(s)=0 только если (sin(pi*Г(s)/s))/(sin(pi/s))=1, ну или sin(pi*Г(s)/s)=sin(pi/s) а это возможно, например, если
pi*Г(s)/s+pi/s=pi ну или Г(s)/s+1/s=1 что всё равно что Г(s)+1=s ну или Г(s)=s-1. нетрудно видеть что подобным свойством обладает знаменитая функция Эйлера, так что, я полагаю, Г(s) это она и есть =)

Спасибо за ответ! Получается что эта функция лишь проверяет является ли число простым.

Anonymous писал(а):Спасибо! Я вчера открыл книжку Мальцева А.И (НГУ) на стр. 59 была формула с оператором минимизации. Кажется это и имелось ввиду.
P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?

Если очень понадобиться, могу встречу с Матиясевичем устроить... =)

Влад писал(а):

Anonymous писал(а):P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?

Если очень понадобиться, могу встречу с Матиясевичем устроить... =)

Да! Давайте у автора спросим! Вернее не совсем автора
ссылка http://intsys.msu.ru/staff/vnosov/theoralg.zip
стр. 76 (последний абзац)
Что это за многочлен!

Немного не так трактовал теорему Матиясевича, сорри.