Множители чисел Мерсенна / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Множители чисел Мерсенна

25 сообщений из 31, страница 1 из 2

все

Множители чисел Мерсенна

#39827668

Gennadiy Usov

Гость

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

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

...

Рейтинг:

0 / 0

18.06.2019, 12:59

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39827795

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

У чисел Мерсенна нет множителей по определению.

...

Рейтинг:

0 / 0

18.06.2019, 15:28

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39827808

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хотя вру. Есть.

...

Рейтинг:

0 / 0

18.06.2019, 15:44

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39827930

Gennadiy Usov

Гость

Из вики:

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

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

...

Рейтинг:

0 / 0

18.06.2019, 19:07

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39827976

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

...

Рейтинг:

0 / 0

18.06.2019, 21:00

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828043

x1ca4064

Участник

Сообщения: 1 191

Рейтинг: 0 / 0

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

Возможно, не понял, но 2 ^(ab)(cd) -1 имеет больше делителей.

...

Рейтинг:

0 / 0

18.06.2019, 23:40

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828071

Gennadiy Usov

Гость

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, а для частного находятся отдельно делители.

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

...

Рейтинг:

0 / 0

19.06.2019, 06:00

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828084

Gennadiy Usov

Гость

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

Есть n1 = n/2

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

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

...

Рейтинг:

0 / 0

19.06.2019, 07:16

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828131

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

довольно немного, даже на очень средненьком

...

Рейтинг:

0 / 0

19.06.2019, 09:12

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828191

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Есть n1 = n/2

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

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

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

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

Для n = 85589933 на наших компах задача скорее всего не решаемая. Возможно ее образцовое решение
потребует вычислительный кластер из множества компов и какие-то методики распараллеливания
этих операций.

...

Рейтинг:

0 / 0

19.06.2019, 10:40

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828217

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

mayton,

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

Код: pascal

1.
2.
3.
4.
5.
6.
7.

v := 1;
for i:= 1 to n1 do begin
  v := v shl 1;
  if v > n then
    v := v - n;
  Writeln(v - 1);
end;

...

Рейтинг:

0 / 0

19.06.2019, 11:14

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828334

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Хм... вычитания. Звучит вкусно.

...

Рейтинг:

0 / 0

19.06.2019, 13:26

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828381

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

19.06.2019, 14:13

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828452

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

почти пол гигабайта текстовой фигни

...

Рейтинг:

0 / 0

19.06.2019, 16:17

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828459

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

19.06.2019, 16:25

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828569

Gennadiy Usov

Гость

...

Рейтинг:

0 / 0

19.06.2019, 21:12

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828595

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

20.06.2019, 00:14

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828621

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

20.06.2019, 06:02

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828647

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

т.е. хочешь проверить являются ли остатки простыми числами? какой смысл?

...

Рейтинг:

0 / 0

20.06.2019, 08:42

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828747

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

20.06.2019, 12:42

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39828940

Gennadiy Usov

Гость

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

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

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

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

...

Рейтинг:

0 / 0

20.06.2019, 20:05

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39829038

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

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

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

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

вообще вроде формула была: n div 2 = 2*a*b + a + b

...

Рейтинг:

0 / 0

21.06.2019, 09:47

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39829068

Gennadiy Usov

Гость

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

...

Рейтинг:

0 / 0

21.06.2019, 10:24

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39829084

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

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

...

Рейтинг:

0 / 0

21.06.2019, 10:52

| Ответить | Цитировать | Написать

Множители чисел Мерсенна

#39829109

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

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

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

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

Тогда можно найти Мр, которые являются простыми числами.Ну попробуйте проверить, что 2 ¹²⁷ -1 простое.
Придется перебирать значения k до 50 000 000 000 000 000. Перебирая по сто миллионов значений в секунду, лет за десять закончите.

...

Рейтинг:

0 / 0

21.06.2019, 11:32

| Ответить | Цитировать | Написать

25 сообщений из 31, страница 1 из 2

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Множители чисел Мерсенна

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=39828131&tid=1339927]:	0ms
get settings:	10ms
get forum list:	15ms
check forum access:	3ms
check topic access:	3ms
track hit:	136ms
get topic data:	9ms
get forum data:	2ms
get page messages:	58ms
get tp. blocked users:	2ms
others:	237ms

total:	475ms