2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 25, 26, 27, 28, 29, 30, 31 ... 46  След.
 
 Re: Поиск простых чисел
Сообщение25.09.2010, 23:26 


27/11/08
109
maxal в сообщении #355809 писал(а):
Ascar в сообщении #355804 писал(а):
какие существуют методы факторизации "псевдопростых чисел по основанию 2" A001567 (кроме чисел Марсена)

Если $n$ псевдопростое по модулю $2$, то есть $2^{n-1}\equiv 1\pmod{n}$ представляем $n-1$ в виде $n-1=2^k m$, где $m$ нечетно и вычисляем $q=2^m\bmod n$ (заметим, что $q^{2^k}\equiv 1\pmod{n}$). Далее последовательным возведением в квадрат находим минимальное такое $t\leq k$, что $q^{2^t}\equiv 1\pmod{n}$. Если $t=0$ или $q^{2^{t-1}}\equiv -1\pmod{n}$, то облом. В противном случае, $\gcd(n,q^{2^{t-1}}-1)$ даст нетривильный множитель $n$.

В случае облома, аналогично можно попробовать найти нетривиальный множитель $m$ - если получится, то делитель $n$ ищется аналогично вышесказанному.


спасибо большое
свои заблуждения осознал полностью :)

мой метод немного сложнее но принцип тотже
зато он позволяет(не методом перебора) находить выражение вида
$2^{p}\equiv 1\pmod{n}$
тоесть находит четное $p$
но основание видимо тут не играет роли, если облом то облом, и нетревиальные множетели по любому основанию неразбегутся :)
хотя $p$ имеет общий делитель с выражением (x-1) где $x$ любой из делителей числа $n$
условно можно считать что полученно больше информации :)

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение27.09.2010, 18:22 
Заблокирован


27/09/10

248
Россия г.Тюмент
Теорема:
числовая прямая может быть бесконечна лишь в том и только том случае если бесконечен ряд простых чисел близнецов. если допустить что пара чисел близнецов конечны числовая прямая будит не бесконечна а конечна при чем заканчиваться она будит последней парой простых чисел близнецов.

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


27/04/09
28128
Вы кое-что забыли. Доказательство.

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


27/06/08
3751
Волгоград
arseniiv в сообщении #356720 писал(а):
Вы кое-что забыли. Доказательство.
А мне кажется, там кое-что лишнее. Формулировка.

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


27/09/10

248
Россия г.Тюмент
Первая основополагающая теорема, которая послужила основанием для создания всех последующих формул и теорем, гласит:
- нельзя разделить всю числовую прямую на одинаково равные отрезки в каждом из которых находилась хотя бы одно простое число.
Это утверждение настолько очевидно и элементарно, что в общем нет надобности доказывать.
В отличие от предположение Лежандр, чья гипотеза предполагает, что между n2 и (n+1)2 располагается, как минимум одно число.
Теорема №3 утверждает, что между n2 и (n+1)2 количество простых чисел не менее чем корень четвертой степени из числа n, каково бы не было n.

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


11/01/06
5561
serega57 в сообщении #357032 писал(а):
Это утверждение настолько очевидно и элементарно, что в общем нет надобности доказывать.

Так не бывает. См. мой теглайн.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение29.09.2010, 07:25 


23/01/07
3355
Новосибирск
serega57 в сообщении #357032 писал(а):
Первая основополагающая теорема, которая послужила основанием для создания всех последующих формул и теорем, гласит:
- нельзя разделить всю числовую прямую на одинаково равные отрезки в каждом из которых находилась хотя бы одно простое число.
Это утверждение настолько очевидно и элементарно, что в общем нет надобности доказывать.

В данной формулировке Ваша теорема - "ни о чем".
Например, я делю числовую прямую на два "одинаково равных отрезка". В каждом из них находится "хотя бы одно простое число". Ваша теорема опровергнута!

Сформулируйте четче то, что Вы имели в виду.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение29.09.2010, 17:35 
Заблокирован


27/09/10

248
Россия г.Тюмент
прошу прощения, что в данный момент не могу ответить на замечания теоремы 3 , потому что плохо владею ПК. приходиться просить кого-нибудь... а пока предлагаю вам теорему №4, которая уж точно никаких сомнений не должна вызвать по поводу ее простоты, как в доказательстве , так и в ее применение. Великий Фебоначи показал, что при проверке какого-либо числа на простату данное число проверяется всеми простыми числами до квадратного корня из этого числа. Смею заверить вас это совершенно не так, никакое из чисел не нуждается в полном использование всех простых делителей меньших квадратного корня из этого числа. Дело в том, что все числа делятся по определенным группам и делители, которые необходимо использовать для проверки простаты, в каждом из этих рядов свои. в качестве примера привожу теорему №4: " Любое число из бесконечного множества чисел, образованных от А квадрат минус а плюс 1 никогда ни одно из этих чисел при своем разложение не будет иметь делителя, имеющего вид 3К+2 , а это как минимум в два раза сокращает проверяемый делитель, но не все числа 3К+1 надо использовать, а лишь только те, которые уже имеются в аналогичных числах ниже лежащих от А до 0." Позже постараюсь ответить на ваши замечания по поводу теоремы №1.

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


11/11/07
1198
Москва
serega57 в сообщении #357347 писал(а):
Великий Фебоначи показал, что при проверке какого-либо числа на простату данное число проверяется всеми простыми числами до квадратного корня из этого числа. Смею заверить вас это совершенно не так, никакое из чисел не нуждается в полном использование всех простых делителей меньших квадратного корня из этого числа.

У Вас несколько устаревшие сведения - со времен Фибоначчи разработано много методов проверки числа на простоту, гораздо более быстрых.

(Оффтоп)

Да и простаты у чисел нет

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


27/11/08
109
1.
добавил новую последовательность
A175865

а основной мой комментарий не приняли :) так сказать весь смысл работы

моя последовательность предполагает нахождение всех элементов другой последовательности A003629
видимо мой английский ужасен
никто не поможет узнать почему комментарии с ссылками на A003629 не приняли, три раза отправлял

-- Сб окт 02, 2010 12:12:55 --
------------------------------------------------------------------------------------------------------------

2.
Построим следующий ряд из простых чисел
пусть $n$ простое число, удовлетворяющее условию
$(x-1)=M*n$
где $x$
$2^{(n-1)}=x(mod (n^{2}))$
а $M$ любое целое больше нуля

например
для M=2 получаем
A175863
для M=3 получаем
A175866

и т.д.

Проверяя $n$ в интервале от $1$ до $2*10^{8}$
и М от $1$ до $999$
обнаружил что получаются последовательности, количество элементов в которых не превышает 5 :)
интересное свойство, даже хочется предположить что так будет всегда, при любых М на всем интервале простых чисел. гармония остатков
можно ли чтонибудь почитать по этому поводу?

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


27/11/08
109
Сегодня нашол еще одно исключение, вида $2^{k}-1$ для последовательности
A175625

$2^{2741333597}-1$
21930668777 - делитель
2741333597 - простое

2741333597 - по сути является элементом последовательности A054723 - псевдопростое число Марсена


незнаю есть ли между $(2^{29}-1)$ и $(2^{2741333597}-1)$ еще псевдопростые вида $(2^{k}-1)$ но то что их много, почти уверен

определить их можно при помощи последовательности

%I A175905
%S A175905 5,29,2045,40133,971837,5063357,7354397,16554917,17786525,42244637,
%T A175905 52717277,79704029
%N A175905 Numbers n such that n=4*(2*i+1)+1, 2^(n-2) = 1(mod (2*i+1))
%K A175905 nonn
%O A175905 1,1
%A A175905 Alzhekeyev Ascar M (allasc(AT)mail.ru), Oct 12 2010

число 2741333597 - является элементом этой последовательности
(почемуто не добавили досих пор в OEIS мою последовательность, поэтому привожу заявку)

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


07/12/10
1
если поиск простых чисел через формулы неэффективен, тогда не проще искать их там, где их точно нет – в результатах таблицы умножения все пропущенные числа простые и доказывать что число простое не надо

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


27/04/09
28128
Какая восхитительная идея!! :o

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


27/11/08
109
еще одна попытка через формулы :)

Условие такое
все числа n удовлетворяющие условию
$2^{n-1}\equiv 1\pmod{n} $
$2^{2*n}\equiv 64\pmod {3*(n+2)}$
$n\equiv 6\pmod{7}$

заявка в OEIS A173654

получаем последовательность
83, 293, 503, 1553, 2393, 3863, 4283, 4703, 6803, 7433, 7853, 9533, 9743, 11213, 12893, 13103, 13313, 14783, 15413, 16253....

все элементы удовлетворяют условию
Primes of the form $2*3*5*7*n+83$
наша последовательность является подпоследовательностью для A141570
-----------------

проверил вручную до 500 миллонов
я знаю что надо проверять по базе псевдопростых по основанию 2
знаю что у некоторых есть такая возможность
немогли бы вы проверить мое условие, наити первые исключения
спасибо за внимание

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение27.12.2010, 17:36 


27/11/08
109
помогли советом
первое исключение 768440063
попробую отыскать следующие исключения

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 682 ]  На страницу Пред.  1 ... 25, 26, 27, 28, 29, 30, 31 ... 46  След.

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



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

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


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

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