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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Есть n1 = n/2

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

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

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

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

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

Есть n1 = n/2

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

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

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


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

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

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

Откуда: Нижневартовск
Сообщений: 6228
 		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
Сообщений: 50489
 		Хм... вычитания. Звучит вкусно.
19 июн 19, 13:26    [21911492]     Ответить | Цитировать Сообщить модератору
 Re: Множители чисел Мерсенна  [new]
Gennadiy Usov
Member

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда: Нижневартовск
Сообщений: 6228
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

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

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

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

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

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

Тогда можно найти Мр, которые являются простыми числами.
Ну попробуйте проверить, что 2127-1 простое.
Придется перебирать значения k до 50 000 000 000 000 000. Перебирая по сто миллионов значений в секунду, лет за десять закончите.
21 июн 19, 11:32    [21912782]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl→      все
Все форумы / Программирование Ответить