2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Тест для чисел Ферма
Сообщение01.09.2024, 12:29 


23/01/07
3497
Новосибирск
Предлагаю гипотетический тест на проверку чисел Ферма на простоту для чисел $F_{n}>17$
$$(2^n-1) = (n+1)+(n+2)+m\cdot (n+3)$$
где $n$ - порядковый номер числа Ферма по принятой здесь классификации,
$m=(0;1;2;3;4....)$.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 12:49 
Заслуженный участник


20/12/10
9042
Батороев
Как-то мутно Вы написали, ничего не понятно. Напишите нормально: число Ферма $F_n=2^{2^n}+1>17$ является простым тогда и только тогда, когда (и дальше Ваше условие).

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 14:56 


23/01/07
3497
Новосибирск
nnosipov
Ну, куда же я без очепяток. Запутался, когда приводил свои расчетные индексы к индексам из Википедии. :oops:
Правильно так:
$$(2^{n}-1) = n+(n+1)+m\cdot (n+2) \eqno (1)$$
где $n$ - порядковый номер числа Ферма по принятой здесь классификации,
$m=(0;1;2;3;4....)$.

Примеры:
1. $F_{3}=2^8+1>17$
Составляем тестовое уравнение:
$(2^{3}-1) = 3+(3+1)+0\cdot (3+2)$
$7=7$
Вывод: число $2^8+1$ - простое.

2. $F_{4}=2^{16}+1$
Составляем тестовое уравнение:
$(2^{4}-1) = 4+(4+1)+1\cdot (4+2)$
$15=15$
Вывод: число $2^{16}+1$ - простое.

3. $F_{5}=2^{32}+1$
Составляем тестовое уравнение:
$(2^{5}-1) = 5+(5+1)+3\cdot (5+2)$
$31\ne 32$
Вывод: число $2^{32}+1$ - не является простым.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:07 
Заслуженный участник


20/08/14
11668
Россия, Москва
Как выбирается $m$?

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:10 
Заслуженный участник


20/12/10
9042
По Вашему тесту выходит, что $F_{16}$ простое. А тест Пепина говорит, что оно составное. И вообще, Ваше условие выполняется, по-видимому, для бесконечно многих $n$, что уже подозрительно.

-- Вс сен 01, 2024 19:12:47 --

Dmitriy40 в сообщении #1652660 писал(а):
Как выбирается $m$?
Вот я просил ТС по-человечески написать условие... Вот оно: $2^n-2n-2 \equiv 0 \pmod{n+2}$. Не нужно никакого $m$.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:20 
Заслуженный участник


20/08/14
11668
Россия, Москва
Батороев
Контрпример: $(2^{16}-1)=16+(16+1)+m(16+2), m=3639$, но $F_{16}=2^{2^{16}}+1$ не простое.
И так же не простые числа Ферма $F_n, n=\{196, 2836, 4551, 5956, 25936, 46775, 65536, 82503, 540736, 598816, 797476\}$ для $n<10^6$. (UPD. Пожалуй тут я погорячился, про них неизвестно простые ли они.)
Не работает тест.
Неужели так трудно было проверить первые два десятка чисел, они же даже менее сотни тысяч, даже без калькулятора можно, на бумажке.

nnosipov
Вы правы, я тоже получил это же условие, гораздо понятнее и проще для проверки.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:21 


23/01/07
3497
Новосибирск
Dmitriy40 в сообщении #1652660 писал(а):
Как выбирается $m$?

Как целое число.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:21 
Заслуженный участник


20/08/14
11668
Россия, Москва
Тестом можно пользоваться лишь как быстрой предварительной проверкой для отсеивания точно составных чисел, ведь одно деление небольших чисел выполнить сильно проще проверки на простоту.
Осталось только доказать корректность теста. Не проверками. А математически.

-- 01.09.2024, 15:22 --

Батороев в сообщении #1652666 писал(а):
Как целое число.
Их бесконечно много, это не ответ.
Но уже и без вас разобрались в вашей идее.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:23 
Заслуженный участник


20/12/10
9042
Dmitriy40
А как проверить, что, например, $F_{196}$ составное? Угадать делитель? Потому как Пепином никак не проверишь.

:facepalm: Я же сам студентам рассказываю как :) Вопрос снимается.

Хотя нет, не снимается. Число-то, мягко говоря, немаленькое, чтобы для него тесты псевдопростоты применять.

Currently it has been shown that 2^(2^k) + 1 is composite for 5 <= k <= 32 (отсюда A019434).

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:42 


23/01/07
3497
Новосибирск
Dmitriy40 в сообщении #1652667 писал(а):
Тестом можно пользоваться лишь как быстрой предварительной проверкой для отсеивания точно составных чисел, ведь одно деление небольших чисел выполнить сильно проще проверки на простоту.

Так я и преследовал такую цель.
Dmitriy40 в сообщении #1652667 писал(а):
Но уже и без вас разобрались в вашей идее.

Ну, Вам и "карты в руки"! Думаю Вы с nnosipovым сумеете развить идею.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:43 
Заслуженный участник


20/08/14
11668
Россия, Москва
Батороев
Вы предложили - Вам и доказывать корректность. Хоть в своей непонятной формулировке, хоть в нормальной.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:47 
Заслуженный участник


20/12/10
9042
Батороев в сообщении #1652674 писал(а):
Думаю Вы с nnosipovым сумеете развить идею.
Не вижу здесь идеи. Таких тестов можно напридумывать сколько хочешь, но будут ли они иметь отношение к реальности? Вряд ли.

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 17:17 


23/02/12
3333
Пусть $A_n$ - событие, что $n$- ое число Ферма является простым. Можно ли считать, что события $A_n$ и $A_{n+1}$ независимы?

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 17:44 


23/01/07
3497
Новосибирск
vicvolf в сообщении #1652694 писал(а):
Пусть $A_n$ - событие, что $n$- ое число Ферма является простым. Можно ли считать, что события $A_n$ и $A_{n+1}$ независимы?

Число Ферма $F_n$ является делителем числа $(F_{n+1}-2)$. Других зависмостей я не наблюдал.
Но я и не знаток, т.к. числами Ферма увлекся всего лишь пару месяцев назад.

-- 01 сен 2024 21:56 --

Dmitriy40 в сообщении #1652675 писал(а):
Батороев
Вы предложили - Вам и доказывать корректность. Хоть в своей непонятной формулировке, хоть в нормальной.

Нормальное доказательство у меня вряд ли получится, а корявое представлять не хочется. Замкнутый круг, однако. :wink:
Предложил тест, по-видимому - вероятностный, да и тем и ограничусь.. пока. Итак, два месяца терзал свои мозги таким хобби. :-)

 Профиль  
                  
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 19:18 
Заслуженный участник


20/08/14
11668
Россия, Москва
Батороев в сообщении #1652695 писал(а):
Предложил тест, по-видимому - вероятностный, да и тем и ограничусь.. пока.
Который ошибся в одной точке из проверенных. И без обоснования ничего не обещает что он не ошибётся в любой из точек $n>33$. В любой! Т.е. это не тест вообще, лишь наблюдение над известными результатами, не аппроксимирующееся дальше, и следовательно ценность нулевая.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: vicvolf


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group