Требуется привести рекурсивно примитивную функцию множеством значений которых является множество простых чисел.
Нашел многочлен с 26 коэффициентами, может кто-нить укажет смысл этих коэффициентов? (http://mindspring.narod.ru/math/ega/Liv/Zagier.htm#ref1)
Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(s)??
Формула простых чисел
Модератор: модераторы
-
- Сообщения: 1615
- Зарегистрирован: Ср, 07 янв 2004, 16:10
- Откуда: PUNK_22_13
- Контактная информация:
Приведу пример такой примитивно рекурсивной функции:
(я расчитываю на то, что вы знакомы с некими начальными понятиями...)
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) .
Вроде всё.
(я расчитываю на то, что вы знакомы с некими начальными понятиями...)
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) .
Вроде всё.
"Ты - мой вопрос на главный ответ!"(с)СЛОТ
She broke my heart.
You merely broke my life.
Я сразу всё, но я ничто.
Я тысячи людей, но я никто...
Превратился в дерьмо, а как обратно - не знаю...
She broke my heart.
You merely broke my life.
Я сразу всё, но я ничто.
Я тысячи людей, но я никто...
Превратился в дерьмо, а как обратно - не знаю...
ИМХО необязательно всё так усложнять, нам ведь надо всего лишь функцию, область значений которой - множество простых чисел. можно взять например такую (за П я обозначил произведение: П(диапазон){выражение}):
F(x)=(x-1)*П(1<i<=x){sgn(rest(x+1,i))}+2
которая будет отдавать число х+1 если х+1 простое и 2-ку в противном случае =)
она примитивно рекурсивна как композиция примитивно рекурсивных функций
F(x)=(x-1)*П(1<i<=x){sgn(rest(x+1,i))}+2
которая будет отдавать число х+1 если х+1 простое и 2-ку в противном случае =)
она примитивно рекурсивна как композиция примитивно рекурсивных функций
f(s)=1-(sin(pi*Г(s)/s))/(sin(pi/s))Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(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) это она и есть =)
Спасибо! Я вчера открыл книжку Мальцева А.И (НГУ) на стр. 59 была формула с оператором минимизации. Кажется это и имелось ввиду.Влад писал(а):Приведу пример такой примитивно рекурсивной Тогда n-е простое число - это наименьшее число, такое, что pp(N)=n+1, т.е. p_N=(минимизация по y)|pp(y)-(N+1)|.
P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?
Сначала подумал, что это похоже на характеристическую функцию множества, потом пригляделся, а там х+1 или 2 в рез-те! Хитро, бравоkaval писал(а):ИМХО необязательно всё так усложнять, нам ведь надо всего лишь функцию, область значений которой - множество простых чисел. можно взять например такую (за П я обозначил произведение: П(диапазон){выражение}):
F(x)=(x-1)*П(1<i<=x){sgn(rest(x+1,i))}+2
которая будет отдавать число х+1 если х+1 простое и 2-ку в противном случае =)
она примитивно рекурсивна как композиция примитивно рекурсивных функций
Спасибо за ответ! Получается что эта функция лишь проверяет является ли число простым.kaval писал(а):f(s)=1-(sin(pi*Г(s)/s))/(sin(pi/s))Преподаватель настаивает на том, что это формула широко известна, вероятно в ней есть sin. По ссылке сверху, указана подобная формула, но что в ней понимать под s, и самое главное Г(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) это она и есть =)
-
- Сообщения: 1615
- Зарегистрирован: Ср, 07 янв 2004, 16:10
- Откуда: PUNK_22_13
- Контактная информация:
Если очень понадобиться, могу встречу с Матиясевичем устроить... =)Anonymous писал(а):Спасибо! Я вчера открыл книжку Мальцева А.И (НГУ) на стр. 59 была формула с оператором минимизации. Кажется это и имелось ввиду.
P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?
"Ты - мой вопрос на главный ответ!"(с)СЛОТ
She broke my heart.
You merely broke my life.
Я сразу всё, но я ничто.
Я тысячи людей, но я никто...
Превратился в дерьмо, а как обратно - не знаю...
She broke my heart.
You merely broke my life.
Я сразу всё, но я ничто.
Я тысячи людей, но я никто...
Превратился в дерьмо, а как обратно - не знаю...
Да! Давайте у автора спросим! Вернее не совсем автораВлад писал(а):Если очень понадобиться, могу встречу с Матиясевичем устроить... =)Anonymous писал(а):P.S: А вот многочлен интересная штучка по теореме Матиясевича сущ. такой многочлен, областью неотрицатльных значений которого явл. простые числа. Интересно, в точности ли совпадают множество простых чисел и множ-во неотриц значений многочлена? И что за 26 параметров, чему их принять равными?
ссылка http://intsys.msu.ru/staff/vnosov/theoralg.zip
стр. 76 (последний абзац)
Что это за многочлен!
Вернуться в «Доска математических объявлений»
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя