Поиск простых чисел

[Ascar]

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$
условно можно считать что полученно больше информации :)

[serega57]

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

[arseniiv]

Вы кое-что забыли. Доказательство.

[VAL]

arseniiv в сообщении #356720 писал(а):

Вы кое-что забыли. Доказательство.

А мне кажется, там кое-что лишнее. Формулировка.

[serega57]

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

[maxal]

serega57 в сообщении #357032 писал(а):

Это утверждение настолько очевидно и элементарно, что в общем нет надобности доказывать.

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

[Батороев]

serega57 в сообщении #357032 писал(а):

Первая основополагающая теорема, которая послужила основанием для создания всех последующих формул и теорем, гласит:
- нельзя разделить всю числовую прямую на одинаково равные отрезки в каждом из которых находилась хотя бы одно простое число.
Это утверждение настолько очевидно и элементарно, что в общем нет надобности доказывать.

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

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

[serega57]

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

[AV_77]

serega57 в сообщении #357347 писал(а):

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

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

(Оффтоп)

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

[Ascar]

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 :)
интересное свойство, даже хочется предположить что так будет всегда, при любых М на всем интервале простых чисел. гармония остатков
можно ли чтонибудь почитать по этому поводу?

[Ascar]

Сегодня нашол еще одно исключение, вида $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 мою последовательность, поэтому привожу заявку)

[tyr]

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

[arseniiv]

Какая восхитительная идея!!

[Ascar]

еще одна попытка через формулы :)

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

[Ascar]

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