2014 dxdy logo

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

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




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1 ... 30, 31, 32, 33, 34, 35, 36 ... 46  След.
 
 
Сообщение18.03.2011, 18:22 


27/11/08
111
mcnuggets в сообщении #424427 писал(а):
К сожалению, списка чисел я не сохранил. Зато поискал первые числа $n$ из более широкого диапазона.

$n > 1000000000000$:
1000194687607 prime
1000871987251 prime
1000905940651 prime
1001504762371 prime
...

$n > 2000000000000$:
2000156766007 prime
2000820812047 prime
2000831929951 prime
...

Все они также простые, однако встречаются все-таки довольно редко.


как находить эти числа да незнаю, поэтому практического смысла мало, но сам факт того что составные числа ненайдены интересен
самое интересное конечно же свойства чисел $m$
ишю описание , пока никто не помог
-------------

посмотрите если не трудно еще одну последовательность
http://dxdy.ru/post422789.html#p422789
эта последовательность возращает гораздо больше простых (плотность на порядок выше) и до 10^15 степени составных я ненашол
может удастся найти составное число вам

 Профиль  
                  
 
 
Сообщение29.03.2011, 16:37 


27/11/08
111
тест для чисел Кармайкла

числа $n$ вида
$n=k*(k+1)/2$

для которых выполняется условие
$p^{n-1}\equiv 1\pmod{n}$
где $p=2^{x}-1$; $p<k$ ($p=1,3,7,15,31,63,127,....$)

заявка в OEIS A188058

получаем последовательность (первые элементы)

(Оффтоп)

115921, 314821, 334153, 8134561, 60957361, 67902031, 329769721, 2489462641, 5444826481, 6200691841, 7121196811, 8801128801, 8863329511, 18147696841, 24151953871, 39799655911, 41355010621, 53799052231, 66873182041, 67643385391, 77347754641, 87838121953, 167385219121, 195858819001, 477539565121, 585796503601, 607820930641, 716851649251, 906414656491, 921323712961, 1219799386081, 1254739472911, 1475132420161, 1664826173011, 2061143303311, 2166765548041, 2565387704881, 2599750649161, 2707561071361, 3316603988251, 3365459571601, 3937585478401, 4072376885851, 4806294337153, 5074002973621, 5133581795161, 5382262315711, 5691713631211, 5738531745871, 5928837516253, 6768261838801, 8154181802341, 12721136974561, 13757013540271, 15836930299081, 19709991455311, 20641350150541, 21396641423653, 23628642996421, 27494801586253, 29246208208561, 31044690270721, 32980205462401, 33896360306161, 35425313925121, 36940119657841, 52801145154253, 59428911555721, 74509837395841, 76209308572321, 81353348106031, 82137251046241, 89647141288321, 95512694882221, 96560434790821, 97860518665561, 100364999815081, 102595270526101, 107699554609921, 111891726943921, 116584274035153, 120085842441601, 121747424737681, 129093421176721, 134456081663611, 136464013562311, 158634268702561, 176347833948721, 176532453985231, 184504394894401...

все полученные значения - числа Кармайкла

причем значение $(k+1)/2$ всегда простое число
$k$ всегда составное

вот вопрос или просьба посчитать посилнее
всегдали мы будем получать Числа Кармайкла
всегда ли $(k+1)/2$ будет простым числом

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение09.05.2011, 12:28 


06/01/10
19
Хотелось бы знать зачем все так усиленно пытаются создать алгоритм поиска простых чисел. Каковы будут последствия, если в один прекрасный день найдется такой алгоритм.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение10.05.2011, 01:17 
Заслуженный участник
Аватара пользователя


09/02/09
2086
Минск, Беларусь
Таких алгоритмов пруд пруди.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение29.05.2011, 16:04 


16/08/05
1146
Возможно для Ascar будет любопытно. Ваш тест для степеней $p$ простых Мерсенна у меня упростился до выражения

$(p-2)^{M-1}\equiv 1\pmod M$

где $M=2^p-1$

В сочетании с другим известным сравнением $3^{M+1}\equiv 9\pmod M$ получается

$(p-2)^{M^2-1}-3^{M^2-1}\equiv 0\pmod M$

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение31.05.2011, 09:45 


16/08/05
1146
До меня дошло )). $(p-2)^{M-1}\equiv 1\pmod M$ - это следствие Малой теоремы Ферма, т.е. вместо $p-2$ может стоять любое взаимно простое с $M$ (только почему-то кроме степеней двойки).
Еще почему-то у меня получилось, что этот тест на основе МТФ фильтрует $p$ быстрее, чем тест Люка-Лемера.

Т.е. код pari/gp
Код:
mtf()=
{
local(M:int);
forprime(p=2, 10^4,
  M= (2^p-1):int;
  if(Mod(3,M)^(M-1)==Mod(1,M),
   print(p)
  )
)
};

выигрывает несколько секунд у кода
Код:
llt()=
{
local(M,s:int);
forprime(p=2, 10^4,
  M= (2^p-1):int;
  s= 4:int;
  for(i=1, p-2, s= (lift(Mod(s,M)^2)-2):int);
  if(s==0, print(p))
)
};

Или тест Люка-Лемера умнее реализуется? Или на диапазоне до 10^5 ситуация изменится?

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение31.05.2011, 12:34 


16/08/05
1146
Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение31.05.2011, 13:06 
Заслуженный участник


20/12/10
8858
dmd в сообщении #452186 писал(а):
Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

Если $M$ --- простое число Мерсенна, то это просто потому, что $3$ --- квадратичный невычет по модулю $M$.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 13:35 


16/08/05
1146
И снова интересно: $p|(M-1)$ и

$3^\frac{M-1}{2p}\equiv -2^x\pmod M$

где $x$ - некое натуральное $<p$

Каким кодом можно быстро определить, что число является степенью двойки?
У меня так сделалось:
Код:
mtf()=
{
local(M,s:int);
forprime(p=3, 4000,
  M= (2^p-1):int;
  s= ((M-1)/2/p):int;
  s= (M-lift(Mod(3,M)^s)):int;
  for(i=1, p-1, if(s==2^i, s= 0:int; break()));
  if(s==0, print(p))
)
};

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 17:42 
Заслуженный участник


20/12/10
8858
dmd в сообщении #452583 писал(а):
И снова интересно: $p|(M-1)$ и

$3^\frac{M-1}{2p}\equiv -2^x\pmod M$

где $x$ - некое натуральное $<p$

И снова это очевидно. Все корни уравнения $x^p+1=0$ в $\mathbb{F}_M$ противоположны корням уравнения $x^p-1=0$, а корни последнего суть $2^a$, где $a=0,1,\ldots,p-1$ (поскольку порядок $2$ по модулю $M$ равен $p$). А $x=3^\frac{M-1}{2p}$ есть один из корней первого уравнения.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 18:31 
Модератор
Аватара пользователя


11/01/06
5660
dmd в сообщении #452583 писал(а):
Каким кодом можно быстро определить, что число является степенью двойки?

Вот так, например:
Код:
if( s==2^valuation(s,2), print("power of 2"); );

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 20:53 


16/08/05
1146
Спасибо за пример и пояснения.

Вот дальше: $3|(M-1)$ для все известных $p$, кроме $p=2$

Удастся ли разглядеть $x$ в сравнении

$3^\frac{M-1}{6p}\equiv x\pmod M$

Для некоторых искомых $p$ он тоже степень двойки.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение03.06.2011, 18:10 


16/08/05
1146
Сумма кубов $a^3+b^3=(a+b)(a^2-ab+b^2)$

Пусть $3|(M-1)$, тогда либо $(a+b):M$, либо $(a^2-ab+b^2):M$,
где $a=3^s$, $s=\frac{M-1}{6p}$ и $b$ - степень двойки.

Соответственно фильтрация $p$ хотя и тормознуто, но работает:

Код:
asc()=
{
local(M,s,t:int);
local(a);
forprime(p=4,4000,
  M= (2^p-1):int;
  s= ((M-1)/6/p):int;
  a= Mod(3,M)^s;
  s= (M-lift(a)):int;
  if(s==2^valuation(s,2), print(p),
   for(i=1, p-1,
    t= (M-lift(a^2-a*Mod(2,M)^i)):int;
    if(t==2^valuation(t,2), print(p); break())
   )
  )
)
};


Если допустим $5|(M-1)$, $a^5+b^5=(a + b) (a^4 - a^3 b + a^2 b^2 - a b^3 + b^4)$, то снова два варианта: либо $(a+b):M$, либо $(a^4 - a^3 b + a^2 b^2 - a b^3 + b^4):M$,
где $a=3^s$, $s=\frac{M-1}{10p}$ и $b$ - степень двойки.

Если простое $q|(M-1)$, $a^q+b^q=(a + b) (a^{q-1} - ... + b^{q-1})$, то та же вилка: либо $(a+b):M$, либо $(a^{q-1} - ... + b^{q-1}):M$,
где $a=3^s$, $s=\frac{M-1}{2qp}$ и $b$ - степень двойки.

)) Быть может нам повезёт и для решения условия $(a^{q-1} - ... + b^{q-1}):M$ найдётся сверхбыстрый алгоритм в теории чисел? Что скажут мастера простых чисел?

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение03.06.2011, 21:30 
Заслуженный участник
Аватара пользователя


09/02/09
2086
Минск, Беларусь
Уже искали :-)

Лучшее, что есть в этой области, - алгоритм AKS: http://en.wikipedia.org/wiki/AKS_primality_test

 Профиль  
                  
 
 Re:
Сообщение04.06.2011, 14:42 
Модератор
Аватара пользователя


11/01/06
5660
Ascar в сообщении #422789 писал(а):
еще один тест

заявка в оеис A187849

нечетные числа n удовлетворяющие условию
$2^{n-1}\equiv 1\pmod{n}$
$2^{m-1}\equiv 1\pmod{m}$
где
$m=n*p-n+1$; $n=2^k*p+1$; $k$ - целое больше нуля, $p$ - целое нечетное число больше нуля

проверил до 10^15, нет ни одного исключения

Вот парочка первых исключений: 1771946607940820033, 14356915031659973281

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 682 ]  На страницу Пред.  1 ... 30, 31, 32, 33, 34, 35, 36 ... 46  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group