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

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

Это интересно?
18 июн 19, 12:59    [21910551]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
У чисел Мерсенна нет множителей по определению.
18 июн 19, 15:28    [21910735]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Хотя вру. Есть.
18 июн 19, 15:44    [21910754]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Из вики:

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

Среди этих чисел Mn есть простые числа, у которых n - есть простое число (не наоборот).
18 июн 19, 19:07    [21910955]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Barlone
Member

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

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

2ab-1 делится на 2a-1 и на 2b-1
Вы знаете больше делителей?
18 июн 19, 21:00    [21911015]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
2ab-1 делится на 2a-1 и на 2b-1
Вы знаете больше делителей?


Возможно, не понял, но 2(ab)(cd)-1 имеет больше делителей.
18 июн 19, 23:40    [21911094]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Barlone
Gennadiy Usov
Можно для чисел Мерсеннна Мn, где n – не является простым числом, найти сомножители для любого n.
Правда, для больших чисел n могут быть найдены не все сомножители.
А для очень больших чисел n найденных сомножителей будет немного.

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

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

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

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

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

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

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

Вопрос закрыт.
19 июн 19, 06:00    [21911139]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Допустим, имеется число (Мерсенна) n = 85589933.

Есть n1 = n/2

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

Сколько потребуется времени на компьютере (очень хорошем), чтобы посчитать величины
от до
?
19 июн 19, 07:16    [21911154]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov,

довольно немного, даже на очень средненьком
19 июн 19, 09:12    [21911210]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Допустим, имеется число (Мерсенна) n = 85589933.

Есть n1 = n/2

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

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

Первая часть формулы считается очень быстро до 2048 бит.


Вангую что будут милисекунды. Потому - как это по сути заполнение единичным битом блок памяти.

Вторая часть формулы где идет операция (mod n) - более тяжелая. Вангую - секунды и минуты до 2048 бит.

Для n = 85589933 на наших компах задача скорее всего не решаемая. Возможно ее образцовое решение
потребует вычислительный кластер из множества компов и какие-то методики распараллеливания
этих операций.
19 июн 19, 10:40    [21911287]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
mayton,

прикалываешься?
O(n) на весь массив, там одни cдвиги и вычитания

v := 1;
for i:= 1 to n1 do begin
  v := v shl 1;
  if v > n then
    v := v - n;
  Writeln(v - 1);
end;
19 июн 19, 11:14    [21911320]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Хм... вычитания. Звучит вкусно.
19 июн 19, 13:26    [21911492]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
kealon(Ruslan)
Gennadiy Usov,
довольно немного, даже на очень средненьком
А точнее, в сек, в мин, в ...., в....,
19 июн 19, 14:13    [21911554]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

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

почти пол гигабайта текстовой фигни
19 июн 19, 16:17    [21911672]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
kealon(Ruslan)
Gennadiy Usov
А точнее, в сек, в мин, в ...., в....,
25 секунд на моём стареньком i7,
фактически со скоростью записи на мой HDD диск
почти пол гигабайта текстовой фигни
Спасибо!
19 июн 19, 16:25    [21911683]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
kealon(Ruslan)
Gennadiy Usov
А точнее, в сек, в мин, в ...., в....,
25 секунд на моём стареньком i7,
фактически со скоростью записи на мой HDD диск
почти пол гигабайта текстовой фигни
А если из n1 перебираются только простые числа?
19 июн 19, 21:12    [21911866]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
А если из n1 перебираются только простые числа?
см 21911320, каким боком туда проверку на простые числа добавить?
20 июн 19, 00:14    [21911925]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

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

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

Наверное, можно запомнить массив простых чисел от 1 до 90 000 000?
20 июн 19, 06:02    [21911959]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov,

т.е. хочешь проверить являются ли остатки простыми числами? какой смысл?
20 июн 19, 08:42    [21911992]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
kealon(Ruslan)
Gennadiy Usov,
т.е. хочешь проверить являются ли остатки простыми числами? какой смысл?
Да, это не то.
Ошибочная ветка.
20 июн 19, 12:42    [21912149]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Как известно, для чисел Мерсенна (вики):

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

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

Тогда можно найти Мр, которые являются простыми числами.
20 июн 19, 20:05    [21912482]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
Как известно, для чисел Мерсенна (вики):

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

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

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

вообще вроде формула была: n div 2 = 2*a*b + a + b
21 июн 19, 09:47    [21912666]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

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

Откуда: Нижневартовск
Сообщений: 5107
Gennadiy Usov
Вот и я спрашиваю, почему нельзя таким образом проверять числа Мерсенна?
а подумать?
21 июн 19, 10:52    [21912737]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Barlone
Member

Откуда:
Сообщений: 1287
Gennadiy Usov
Как известно, для чисел Мерсенна (вики):

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

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

Тогда можно найти Мр, которые являются простыми числами.
Ну попробуйте проверить, что 2127-1 простое.
Придется перебирать значения k до 50 000 000 000 000 000. Перебирая по сто миллионов значений в секунду, лет за десять закончите.
21 июн 19, 11:32    [21912782]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

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

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

Откуда:
Сообщений: 1693
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

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

В этом тесте есть начальное число – 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

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

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

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

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

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

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

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

Откуда:
Сообщений: 1693
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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить