Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | |
---|---|---|
xsx |
|
|
Подскажите возможно ли математически без перебора, проверить является ли число остатком от деления при тесте Люка — Лемера? Например является ли 133 числом среди: ([math]4^{2} -2)\mod 8191=14[/math] ([math]14^{2} -2)\mod 8191=194[/math] ([math]194^{2} -2)\mod 8191=4870[/math] ([math]4870^{2} -2)\mod 8191=3953[/math] ([math]3953^{2} -2)\mod 8191=5970[/math] ([math]5970^{2} -2)\mod 8191=1857[/math] ([math]1857^{2} -2)\mod 8191=36[/math] ([math]36^{2} -2)\mod 8191=1294[/math] ([math]1294^{2} -2)\mod 8191=3470[/math] ([math]3470^{2} -2)\mod 8191=128[/math] ([math]128^{2} -2)\mod 8191=0[/math] наглядно или перебором найти не проблема, но можно ли описать это с помощью математики? Например при помощи области определений. Более интересует случай, когда искомое число зависит от 8191 по какой-либо формуле: например является ли (8191+1)/4 одним из остатков на деления. |
||
Вернуться к началу | ||
Grigory110 |
|
|
Добрый день,
А еще лучше найти и остаток и его номер в тесте. В тесте Люка-Лемера нужно сделать [math]P-2[/math] вычислений для поиска остатка, и было бы круто найти сразу остаток для шага [math]P-3[/math]. Эх, если бы было так, то тест проверял бы числа Мерсена на простоту за время двух умножений на компьютере. Насколько я знаю, реальность сурова, и такого алгоритма нет. Поэтому первое число для поиска остатков берут отсюда https://oeis.org/A018844. Кстати, попробуйте изучить все свойства последовательности Люки, т.к. тест LL полностью базируется на них. |
||
Вернуться к началу | ||
xsx |
|
|
Большое спасибо за ответ.
А я то думал) Научился проверять число Мерсена по предпоследнему делителю, так, думаю, сейчас умнее всех сделаюсь, а нет - выходит как обычно ) получается мой метод, только уберет 1 итерацию в конце самом( |
||
Вернуться к началу | ||
Grigory110 |
|
|
Добрый день.
xsx писал(а): получается мой метод, только уберет 1 итерацию в конце самом( Задача теста заключается в том, чтобы сказать, что остаток от деления на итерации [math]P-3[/math] равен нулю. Боюсь, что такого способа нет. |
||
Вернуться к началу | ||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Связь от числа факториала и остатком его деления на x
в форуме Теория чисел |
4 |
417 |
17 окт 2020, 00:18 |
|
Узнать остаток от деления степени на число
в форуме Алгебра |
10 |
808 |
30 дек 2018, 20:42 |
|
Является ли простым число
в форуме Алгебра |
7 |
319 |
14 апр 2021, 14:43 |
|
Является ли число полным квадратом?
в форуме Теория чисел |
2 |
917 |
25 мар 2019, 17:51 |
|
Доказать, что число является составным
в форуме Алгебра |
3 |
492 |
08 мар 2018, 21:23 |
|
Доказать, что число является факториалом | 3 |
93 |
04 мар 2024, 17:31 |
|
Помощь на тесте
в форуме Размышления по поводу и без |
0 |
170 |
05 май 2021, 14:32 |
|
Доказать, что число sqrt(X) является иррациональным
в форуме Алгебра |
3 |
930 |
20 дек 2016, 11:34 |
|
Доказать, что число является корнем уравнения
в форуме Тригонометрия |
28 |
1214 |
27 авг 2017, 14:12 |
|
Доказательство теоремы Люка
в форуме Теория чисел |
2 |
246 |
15 июн 2021, 06:46 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |