Тест для чисел Ферма

[Батороев]

Предлагаю гипотетический тест на проверку чисел Ферма на простоту для чисел $F_{n}>17$

$$(2^n-1) = (n+1)+(n+2)+m\cdot (n+3)$$

где $n$ - порядковый номер числа Ферма по принятой здесь классификации,
$m=(0;1;2;3;4....)$.

[nnosipov]

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

[Батороев]

nnosipov
Ну, куда же я без очепяток. Запутался, когда приводил свои расчетные индексы к индексам из Википедии.
Правильно так:

$$(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$ - не является простым.

[Dmitriy40]

Как выбирается $m$?

[nnosipov]

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

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

Dmitriy40 в сообщении #1652660 писал(а):

Как выбирается $m$?

Вот я просил ТС по-человечески написать условие... Вот оно: $2^n-2n-2 \equiv 0 \pmod{n+2}$. Не нужно никакого $m$.

[Dmitriy40]

Батороев
Контрпример: $(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
Вы правы, я тоже получил это же условие, гораздо понятнее и проще для проверки.

[Батороев]

Dmitriy40 в сообщении #1652660 писал(а):

Как выбирается $m$?

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

[Dmitriy40]

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

-- 01.09.2024, 15:22 --

Батороев в сообщении #1652666 писал(а):

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

Их бесконечно много, это не ответ.
Но уже и без вас разобрались в вашей идее.

[nnosipov]

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

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

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

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

[Батороев]

Dmitriy40 в сообщении #1652667 писал(а):

Тестом можно пользоваться лишь как быстрой предварительной проверкой для отсеивания точно составных чисел, ведь одно деление небольших чисел выполнить сильно проще проверки на простоту.

Так я и преследовал такую цель.

Dmitriy40 в сообщении #1652667 писал(а):

Но уже и без вас разобрались в вашей идее.

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

[Dmitriy40]

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

[nnosipov]

Батороев в сообщении #1652674 писал(а):

Думаю Вы с nnosipovым сумеете развить идею.

Не вижу здесь идеи. Таких тестов можно напридумывать сколько хочешь, но будут ли они иметь отношение к реальности? Вряд ли.

[vicvolf]

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

[Батороев]

vicvolf в сообщении #1652694 писал(а):

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

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

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

Dmitriy40 в сообщении #1652675 писал(а):

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

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

[Dmitriy40]

Батороев в сообщении #1652695 писал(а):

Предложил тест, по-видимому - вероятностный, да и тем и ограничусь.. пока.

Который ошибся в одной точке из проверенных. И без обоснования ничего не обещает что он не ошибётся в любой из точек $n>33$. В любой! Т.е. это не тест вообще, лишь наблюдение над известными результатами, не аппроксимирующееся дальше, и следовательно ценность нулевая.