2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 2^50372821-1 is prime?
Сообщение15.09.2009, 21:44 
Разложить два числа на простые сомножители: 36174685195241609307058623156071588556919160765478402098322496201601656672345474748759325284881827046590027356516803981899593124234415938475264682618329 и
число:42729794125603525715143055547841755483092995668000178402159721819058632946212934122634358810443369654903315680919422431965254993373625934146121568340753562075777160944543303827990114633443890559976621265769179050210849285847094060862552713771186929087048796695403458626692604101003089934482615751828110936790711988167546352565987439985381127671490569976918658381997 и возможно этих данных хватит, чтобы доказать или опровергнуть с помощью регулярного метода,
является ли число 2^50372821-1 is prime или composite! Возможны дополнительные вычисления!

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение15.09.2009, 21:53 
Аватара пользователя

(Оффтоп)

Надо дождаться SerjeyMinsk. Его алгоритм такие числа, как орешки щелкает. А Вы бы разбили числа пробелами через 9, а то читать неудобно.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение15.09.2009, 22:36 
Anatolii в сообщении #243677 писал(а):
Разложить два числа на простые сомножители:
А вам обязательно множители нужны, или достаточно того, что они составные.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение15.09.2009, 23:07 
Аватара пользователя
Первое можно дня за 4 щёлкнуть GNFS, но знать бы, зачем?

У меня на очереди дофига других чисел :-)
Anatolii в сообщении #243677 писал(а):
является ли число 2^50372821-1 is prime или composite!
Оно делится на 10059956081911.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение15.09.2009, 23:40 
Anatolii в сообщении #243677 писал(а):
Разложить два числа на простые сомножители: 36174685195241609307058623156071588556919160765478402098322496201601656672345474748759325284881827046590027356516803981899593124234415938475264682618329 и
число:42729794125603525715143055547841755483092995668000178402159721819058632946212934122634358810443369654903315680919422431965254993373625934146121568340753562075777160944543303827990114633443890559976621265769179050210849285847094060862552713771186929087048796695403458626692604101003089934482615751828110936790711988167546352565987439985381127671490569976918658381997
Оба составные, что Maple определяет примерно за одну тысячную секунды (Gris, выкиньте свой Excel :) ). А с конкретным разложением "немного" посложнее.
Цитата:
возможно этих данных хватит, чтобы доказать или опровергнуть с помощью регулярного метода,
является ли число 2^50372821-1 is prime или composite! Возможны дополнительные вычисления!
За этим к GIMPS. Они, как раз, примерно до таких чисел добрались. То, что у меня сейчас считается лишь немного (хотя это как считать :) поменьше.

-- 16 сен 2009, 01:52 --

Droog_Andrey в сообщении #243690 писал(а):
Anatolii в сообщении #243677 писал(а):
является ли число 2^50372821-1 is prime или composite!
Оно делится на 10059956081911.

И правда!
Андрей! А Вы это знали или быстренько в уме прикинули? :)

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 02:00 
Аватара пользователя
Делители числа $2^p - 1$, где $p$ простое, имеют вид $2kp+1$ ($k$ - целое).
$$ 10059956081911 = 2\cdot 99855\cdot 50372821 + 1.$$

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 10:56 
Согласно данному методу можно найти и меньший делитель, возьмём пример 2*65*50372821+1=6548466731 и из него получаем, что 2^50372821-1
делится на 6548466731. Не всё очевидно, что только вероятно! Впрочем у меня нет такой программы, чтобы проверить это!

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 11:34 
maxal в сообщении #243709 писал(а):
Делители числа $2^p - 1$, где $p$ простое, имеют вид $2kp+1$ ($k$ - целое).
$$ 10059956081911 = 2\cdot 99855\cdot 50372821 + 1.$$
Угу.
Цикл до 100000 с бинарным возведением с степень по модулю, вполне посильная задача. У меня на компе за 7 секунд сосчиталось.
-- 16 сен 2009, 13:36 --

Anatolii в сообщении #243762 писал(а):
Согласно данному методу можно найти и меньший делитель, возьмём пример 2*65*50372821+1=6548466731 и из него получаем, что 2^50372821-1
делится на 6548466731. Не всё очевидно, что только вероятно! Впрочем у меня нет такой программы, чтобы проверить это!
А у меня такая программа есть.
Поэтому я утверждаю, что 6548466731 делителем не является, а делитель, приведенный Андреем - наименьший.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 15:28 
Аватара пользователя
Anatolii в сообщении #243762 писал(а):
Впрочем у меня нет такой программы, чтобы проверить это!

Возьмите бесплатную PARI/GP - см. topic14229.html
Код на ней примерной такой:
Код:
? p=50372821; for(k=1,10^6, if( Mod(2,2*k*p+1)^p == 1, print([k,2*k*p+1]); ); )
[99855, 10059956081911]
? ##
  ***   last result computed in 1,272 ms.

Таким образом, чтобы перебрать значения $k \leq 10^6$ потребовалось чуть более секунды.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 19:06 
Аватара пользователя
VAL в сообщении #243694 писал(а):
Андрей! А Вы это знали или быстренько в уме прикинули? :)
Поиск делителя с помощью Prime95 занял менее секунды.

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 19:37 
Droog_Andrey в сообщении #243904 писал(а):
VAL в сообщении #243694 писал(а):
Андрей! А Вы это знали или быстренько в уме прикинули? :)
Поиск делителя с помощью Prime95 занял менее секунды.
Prime95 и у меня стоит. Но у меня он считает то, что сам хочет (или то, чего GIMPS хочет), у меня не спрашивает :)

 
 
 
 Re: 2^50372821-1 is prime?
Сообщение16.09.2009, 19:51 
Аватара пользователя
Вся фишка в файлике worktodo.txt :wink:

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group