Можно для чисел Мерсеннна Мn, где n – не является простым числом, найти сомножители для любого n.
Правда, для больших чисел n могут быть найдены не все сомножители.
А для очень больших чисел n найденных сомножителей будет немного.

Это интересно?

Из вики:

числа Мерсенна имеют вид Мn = 2^n-1.

Среди этих чисел Mn есть простые числа, у которых n - есть простое число (не наоборот).

BarloneGennadiy UsovМожно для чисел Мерсеннна Мn, где n – не является простым числом, найти сомножители для любого n.
Правда, для больших чисел n могут быть найдены не все сомножители.
А для очень больших чисел n найденных сомножителей будет немного.

Это интересно?
2 ^ab -1 делится на 2 ^a -1 и на 2 ^b -1
Вы знаете больше делителей?Например:

2^22 - 1 = 4194303 = 3 * 23 * 89 * 683

То есть, добавляется 683.

С другой стороны, спасибо за формулу!

Не обратил на неё внимание.

Получается, 2 ^ab -1 делится на 2 ^a -1 и на 2 ^b -1, а для частного находятся отдельно делители.

Вопрос закрыт.

Допустим, имеется число (Мерсенна) n = 85589933.

Есть n1 = n/2

У меня вопрос:

Сколько потребуется времени на компьютере (очень хорошем), чтобы посчитать величины
от до
?

kealon(Ruslan)Gennadiy Usov,
довольно немного, даже на очень средненькомА точнее, в сек, в мин, в ...., в....,

kealon(Ruslan)Gennadiy UsovА точнее, в сек, в мин, в ...., в....,25 секунд на моём стареньком i7,
фактически со скоростью записи на мой HDD диск
почти пол гигабайта текстовой фигниСпасибо!

kealon(Ruslan)Gennadiy UsovА точнее, в сек, в мин, в ...., в....,25 секунд на моём стареньком i7,
фактически со скоростью записи на мой HDD диск
почти пол гигабайта текстовой фигниА если из n1 перебираются только простые числа?

kealon(Ruslan)Gennadiy UsovА если из n1 перебираются только простые числа?см 21911320 , каким боком туда проверку на простые числа добавить?Проверка не нужна.

Просто выбираются простые числа из некоторого массива.

Наверное, можно запомнить массив простых чисел от 1 до 90 000 000?

kealon(Ruslan)Gennadiy Usov,
т.е. хочешь проверить являются ли остатки простыми числами? какой смысл?Да, это не то.
Ошибочная ветка.

Как известно, для чисел Мерсенна (вики):

«Любой делитель составного числа Mр для простого p имеет вид 2*k*p +1, где k – натуральное число.»

Спрашивается:
почему нельзя для каждого Мр (начиная с р = 2) перебирать числа с целью поиска делителя (наименьшего)?
При этом делитель не будет превышать числа, которое получается после деления.

Тогда можно найти Мр, которые являются простыми числами.

kealon(Ruslan)Gennadiy UsovКак известно, для чисел Мерсенна (вики):
«Любой делитель составного числа Mр для простого p имеет вид 2*k*p +1, где k – натуральное число.»
Спрашивается:
почему нельзя для каждого Мр (начиная с р = 2) перебирать числа с целью поиска делителя (наименьшего)?
При этом делитель не будет превышать числа, которое получается после деления.
Тогда можно найти Мр, которые являются простыми числами.можно наверное. Вопрос: размер такого перебора какой?
вообще вроде формула была: n div 2 = 2*a*b + a + b Вот и я спрашиваю, почему нельзя таким образом проверять числа Мерсенна?

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

А сколько Мр можно будет проверить таким методом?

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

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

Можно назвать это решетом - постепенное "выбивание не простых Мр" .

Решил поработать с тестом Люка-Лемера.

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

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

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

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

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

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

Наверное, тест Люка-Лемера по сравнению с тестом Пепина при начальном числе 5 будет быстрее.

Ещё один вопрос.

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

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

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

И естественно, далее, для других чисел.

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

2 ^a+a -1 = (2 ^a -1) * (2 ^a +1)