Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Является ли число остатком от деления при тесте Люка—Лемера
СообщениеДобавлено: 24 ноя 2016, 08:37 
Не в сети
Начинающий
Зарегистрирован:
24 ноя 2016, 08:30
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день, друзья.
Подскажите возможно ли математически без перебора, проверить является ли число остатком от деления при тесте Люка — Лемера?
Например является ли 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 одним из остатков на деления.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Является ли число остатком от деления при тесте Люка—Лемера
СообщениеДобавлено: 25 ноя 2016, 11:21 
Не в сети
Продвинутый
Зарегистрирован:
27 окт 2016, 23:23
Сообщений: 61
Cпасибо сказано: 3
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день,

А еще лучше найти и остаток и его номер в тесте.

В тесте Люка-Лемера нужно сделать [math]P-2[/math] вычислений для поиска остатка, и было бы круто найти сразу остаток для шага [math]P-3[/math]. Эх, если бы было так, то тест проверял бы числа Мерсена на простоту за время двух умножений на компьютере.

Насколько я знаю, реальность сурова, и такого алгоритма нет. Поэтому первое число для поиска остатков берут отсюда https://oeis.org/A018844.
Кстати, попробуйте изучить все свойства последовательности Люки, т.к. тест LL полностью базируется на них.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Является ли число остатком от деления при тесте Люка—Лемера
СообщениеДобавлено: 25 ноя 2016, 22:39 
Не в сети
Начинающий
Зарегистрирован:
24 ноя 2016, 08:30
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Большое спасибо за ответ.
А я то думал) Научился проверять число Мерсена по предпоследнему делителю, так, думаю, сейчас умнее всех сделаюсь, а нет - выходит как обычно :))
получается мой метод, только уберет 1 итерацию в конце самом(

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Является ли число остатком от деления при тесте Люка—Лемера
СообщениеДобавлено: 28 ноя 2016, 17:54 
Не в сети
Продвинутый
Зарегистрирован:
27 окт 2016, 23:23
Сообщений: 61
Cпасибо сказано: 3
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день.

xsx писал(а):
получается мой метод, только уберет 1 итерацию в конце самом(

Задача теста заключается в том, чтобы сказать, что остаток от деления на итерации [math]P-3[/math] равен нулю. Боюсь, что такого способа нет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Связь от числа факториала и остатком его деления на x

в форуме Теория чисел

SiFlyer

4

416

17 окт 2020, 00:18

Узнать остаток от деления степени на число

в форуме Алгебра

Djwiccdeqd

10

808

30 дек 2018, 20:42

Является ли простым число

в форуме Алгебра

tata00tata

7

319

14 апр 2021, 14:43

Является ли число полным квадратом?

в форуме Теория чисел

Claudia

2

917

25 мар 2019, 17:51

Доказать, что число является составным

в форуме Алгебра

alekscooper

3

492

08 мар 2018, 21:23

Доказать, что число является факториалом

в форуме Интересные задачи участников форума MHP

Xenia1996

3

93

04 мар 2024, 17:31

Помощь на тесте

в форуме Размышления по поводу и без

DorisNoris

0

170

05 май 2021, 14:32

Доказать, что число sqrt(X) является иррациональным

в форуме Алгебра

Fireman

3

930

20 дек 2016, 11:34

Доказать, что число является корнем уравнения

в форуме Тригонометрия

slog

28

1214

27 авг 2017, 14:12

Доказательство теоремы Люка

в форуме Теория чисел

gorauralsk

2

246

15 июн 2021, 06:46


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved