2014 dxdy logo

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

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




На страницу Пред.  1 ... 30, 31, 32, 33, 34, 35, 36 ... 46  След.
 
 
Сообщение18.03.2011, 18:22 
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 
тест для чисел Кармайкла

числа $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 
Хотелось бы знать зачем все так усиленно пытаются создать алгоритм поиска простых чисел. Каковы будут последствия, если в один прекрасный день найдется такой алгоритм.

 
 
 
 Re: Поиск простых чисел
Сообщение10.05.2011, 01:17 
Аватара пользователя
Таких алгоритмов пруд пруди.

 
 
 
 Re: Поиск простых чисел
Сообщение29.05.2011, 16:04 
Возможно для 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 
До меня дошло )). $(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 
Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

 
 
 
 Re: Поиск простых чисел
Сообщение31.05.2011, 13:06 
dmd в сообщении #452186 писал(а):
Интересно, что $3^\frac{M-1}{2}\equiv -1\pmod M$

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

 
 
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 13:35 
И снова интересно: $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 
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 
Аватара пользователя
dmd в сообщении #452583 писал(а):
Каким кодом можно быстро определить, что число является степенью двойки?

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

 
 
 
 Re: Поиск простых чисел
Сообщение01.06.2011, 20:53 
Спасибо за пример и пояснения.

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

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

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

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

 
 
 
 Re: Поиск простых чисел
Сообщение03.06.2011, 18:10 
Сумма кубов $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 
Аватара пользователя
Уже искали :-)

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

 
 
 
 Re:
Сообщение04.06.2011, 14:42 
Аватара пользователя
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