2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Тест для чисел Ферма
Сообщение01.09.2024, 12:29 
Предлагаю гипотетический тест на проверку чисел Ферма на простоту для чисел $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 
Батороев
Как-то мутно Вы написали, ничего не понятно. Напишите нормально: число Ферма $F_n=2^{2^n}+1>17$ является простым тогда и только тогда, когда (и дальше Ваше условие).

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 14:56 
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 
Как выбирается $m$?

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:10 
По Вашему тесту выходит, что $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 
Батороев
Контрпример: $(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 
Dmitriy40 в сообщении #1652660 писал(а):
Как выбирается $m$?

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

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:21 
Тестом можно пользоваться лишь как быстрой предварительной проверкой для отсеивания точно составных чисел, ведь одно деление небольших чисел выполнить сильно проще проверки на простоту.
Осталось только доказать корректность теста. Не проверками. А математически.

-- 01.09.2024, 15:22 --

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

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:23 
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 
Dmitriy40 в сообщении #1652667 писал(а):
Тестом можно пользоваться лишь как быстрой предварительной проверкой для отсеивания точно составных чисел, ведь одно деление небольших чисел выполнить сильно проще проверки на простоту.

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

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

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:43 
Батороев
Вы предложили - Вам и доказывать корректность. Хоть в своей непонятной формулировке, хоть в нормальной.

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 15:47 
Батороев в сообщении #1652674 писал(а):
Думаю Вы с nnosipovым сумеете развить идею.
Не вижу здесь идеи. Таких тестов можно напридумывать сколько хочешь, но будут ли они иметь отношение к реальности? Вряд ли.

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 17:17 
Пусть $A_n$ - событие, что $n$- ое число Ферма является простым. Можно ли считать, что события $A_n$ и $A_{n+1}$ независимы?

 
 
 
 Re: Тест для чисел Ферма
Сообщение01.09.2024, 17:44 
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 
Батороев в сообщении #1652695 писал(а):
Предложил тест, по-видимому - вероятностный, да и тем и ограничусь.. пока.
Который ошибся в одной точке из проверенных. И без обоснования ничего не обещает что он не ошибётся в любой из точек $n>33$. В любой! Т.е. это не тест вообще, лишь наблюдение над известными результатами, не аппроксимирующееся дальше, и следовательно ценность нулевая.

 
 
 [ Сообщений: 36 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group