Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1585
kealon(Ruslan)
Gennadiy Usov
Вот и я спрашиваю, почему нельзя таким образом проверять числа Мерсенна?
а подумать?
То есть, всё упирается во время расчетов?

А сколько Мр можно будет проверить таким методом?
21 июн 19, 11:34    [21912785]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1585
Barlone
Gennadiy Usov
Как известно, для чисел Мерсенна (вики):
«Любой делитель составного числа Mр для простого p имеет вид 2*k*p +1, где k – натуральное число.»
Спрашивается:
почему нельзя для каждого Мр (начиная с р = 2) перебирать числа с целью поиска делителя (наименьшего)?
При этом делитель не будет превышать числа, которое получается после деления.
Тогда можно найти Мр, которые являются простыми числами.
Ну попробуйте проверить, что 2127-1 простое.
Придется перебирать значения k до 50 000 000 000 000 000. Перебирая по сто миллионов значений в секунду, лет за десять закончите.
Зачем уже сразу 127?

Можно "окучить" окружение 127 (и любое другое окружение), то есть "работать" до некоторого небольшого числа k, и "осмотреться".

Можно назвать это решетом - постепенное "выбивание не простых Мр" .
21 июн 19, 12:48    [21912872]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1585
Решил поработать с тестом Люка-Лемера.

В этом тесте есть начальное число – 4. (может быть и 10, 52, …)

Числа Мерсенна имеют вид 2^р – 1.
С помощью теста Люка-Лемера определяются простые числа Мерсенна.

Меня заинтересовало число 17 (р=4), следующее нечетное за число Мерсенна
То есть 2^р + 1.

Для числа 17 нашел новое число для теста Люка-Лемера – 5.

Оказалось, что при начальном числе 5 тест Люка-Лемера находит следующие числа
17(р=4), 257(р=8), 65537(р=16).


Это есть числа Ферма, которых только 5 (ещё 3 и 5).

Наверное, тест Люка-Лемера по сравнению с тестом Пепина при начальном числе 5 будет быстрее.
27 июн 19, 06:59    [21915902]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1585
Ещё один вопрос.

Есть тест Люка-Лемера.

Как уже говорилось на форуме, в компьютере можно представить целое число любой длины.

Тогда почему есть трудности для определения простоты число Мр, р = 82 589 933?
Ведь всего 82 589 933 вычислений чисел теста Люка-Лемера.

И естественно, далее, для других чисел.
3 июл 19, 13:16    [21919792]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47948
Gennadiy Usov
Тогда почему есть трудности для определения простоты число Мр, р = 82 589 933?
Ведь всего 82 589 933 вычислений чисел теста Люка-Лемера.

Во времени, необходимом для этой операции.
3 июл 19, 14:54    [21919933]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1585
Barlone
Gennadiy Usov
Можно для чисел Мерсеннна Мn, где n – не является простым числом, найти сомножители для любого n.
Правда, для больших чисел n могут быть найдены не все сомножители.
А для очень больших чисел n найденных сомножителей будет немного.
Это интересно?
2ab-1 делится на 2a-1 и на 2b-1
Вы знаете больше делителей?
Не просто делится.

2a+a-1 = (2a-1) * (2a+1)
7 июл 19, 05:16    [21922151]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / Программирование Ответить