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

[DiviSer]

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

[Ascar]

Ascar в сообщении #341829 писал(а):

а самое главное $i+3$ имеет сильный! делитель $2^{23}+1$

извините ошибся
$i+3$ имеет делитель $2^{23}-1$
сильный делитель имеет вид $(2^{23}+1)/3$

все немного сложнее..но всеравно интересно

[Skipper]

(разжигание флейма)

DiviSer
По-моему, он сам не знает, что он считает.
Вот вы сами подумайте, что может решать человек, который пишет вот это --

Цитата:

Просто 10 значные он считает за секунду.
Почему увеличивается время для 100 значного аж в $10^{25}$ больше возраста вселенной я никак понять не могу. Один ноль добавляется.

Это же самый великий перл форума dxdy.ru!
Т.е. человек не понимает, что такое $10^{100}$, и чем оно отличается от $10^{10}$. Он думает, один ноль добавляется - и это немного. Насколько чудовищно огромное число $10^{100}$ (т.е. 100-значное), и что это больше чем количество атомов во Вселенной, я понимал уже в 6-м классе средней школы... :)

Когда у товарища SerjeyMinsk попросили НЕСКОЛЬКО РАЗ определить с помощью ASSA, простые ли числа в примере (там были большие, длинные числа, 100-значные, 300-значные и др.), он даже не смог ничего ответить. А лучшие алгоритмы определят это на компьютере за считанные минуты. И он наверное не понимает, что ценны именно ДЛИННЫЕ, большие простые числа, а маленькие, до $10^{10}$, и даже до $10^{50}$ не нужны никому. Их можно при желании определить за мгновение.

[SerjeyMinsk]

(флейм)

Skipper, судя по всему Вы так в 6 классе и остались.
Ответ был про возраст вселенной, что очень меня насмешило в виду того, что самого возраста вселенной никто и не знает-то, зато все мастера в пример приводить. Ну вот прям, как и Вы про число атомов в той-же вселенной. Да само понятие Вселенной-то наверняка не понимаете, а все туда-же.
Сказки о очень больших числах, которые якобы кому-то нужны Вы их себе сочиняйте. Я так далеко от этих чисел о которых Вы тут говорите, что для меня они не такие уж и большие, как думается. Я работаю над бесконечно большими числами, а Вы тут мне про прошлый век говорите.
Поймите, что математика сплошь и рядом на символах построена.
Есть числа 1,2,3,4,5 и т.д, есть числа в степени, но нет чисел типа 1/2 - это отношение чисел. Также как и число и множество - это одно и тоже. И основали математику любители, а не специалисты. Вот когда с 6 класса выберетесь, переходите сразу на эти понятия и многое Вам в математике откроется нового и интересного.

[mihailm]

(флейм)

SerjeyMinsk в сообщении #342191 писал(а):

Также как и число и множество - это одно и тоже

Пифагор кажется говорил - все есть число
Отсюда ясен перец следует что и множество число

P.S. У меня только одно сомнение - подмножество это число или все-таки подчисло?

[Skipper]

(флейм)

Цитата:

самого возраста вселенной никто и не знает-то

Знают. Возраст Вселенной около 14 млрд лет. Изучите космологию, и поймете даже, как это можно узнать.

Цитата:

Сказки о очень больших числах, которые якобы кому-то нужны Вы их себе сочиняйте.

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

Цитата:

Я работаю над бесконечно большими числами

Какими-какими числами? :) И ГДЕ и КАК вы работаете с этими числами? Неужели с помощью ASSA?

Цитата:

Есть числа 1,2,3,4,5 и т.д, есть числа в степени, но нет чисел типа 1/2 - это отношение чисел.

Нет, уважаемый, вы ошибаетесь. Числа 1,2,3,4,5 - НАТУРАЛЬНЫЕ числа, их множество обозначается буквой N. Есть еще ЦЕЛЫЕ числа, которые включают кроме натуральных (>0) - нуль и отрицательные, т.е. 0,-1,-2,-3... Это расширенное множество чисел обозначается буквой Z. Далее, существует еще одно расширение множества чисел, которое кроме целых, включает еще дробные числа - они являются результатом делания каких-то целых, например, -3, 0, 2, 1/2==0,5, 1/3==0,33333.... - это все РАЦИОНАЛЬНЫЕ числа, и это множество обозначается буквой Q. Кроме этого, существуют еще ИРРАЦИОНАЛЬНЫЕ числа, например число ПИ, корни из чисел и т.д. Их нельзя представить виде обыкновенной дроби, в которой в числителе и знаменателе - целые числа. ИРРАЦИОНАЛЬНЫЕ в свою очередь могут быть ТРАНСЦЕНДЕНТНЫМИ, АЛГЕБРАИЧЕСКИМИ, и др. Есть числа которые вообще нельзя описать какой-то конечной цепочкой определий. И РАЦИОНАЛЬНЫЕ+ИРРАЦИОНАЛЬНЫЕ представляют собой множество R - это действительные числа! И это еще не все. Есть множество комплексных чисел, которое обозначается буквой C. По крайней мере, в школе изучаются все, кроме комплексных. А вы не знаете даже про рациональные (Q). Теперь, внимание, вопрос - кто из нас остался в 6-м классе?

[SerjeyMinsk]

(флейм)

DiviSer
Не заметил сообщение.
Первый вариант, который Вы указали.

-- Вт авг 03, 2010 15:40:31 --

mihailm в сообщении #342209 писал(а):

SerjeyMinsk в сообщении #342191 писал(а):

Также как и число и множество - это одно и тоже

Пифагор кажется говорил - все есть число
Отсюда ясен перец следует что и множество число

P.S. У меня только одно сомнение - подмножество это число или все-таки подчисло?

Множество натуральных чисел, является натуральным числом, но оно не является элементом самого себя так как элементами множества натуральных чисел являются конечные числа, а само множество натуральных чисел бесконечно.

[Skipper]

(флейм)

Цитата:

Множество натуральных чисел, является натуральным числом

Что ни фраза, то перл!
SerjeyMinsk, почему бы вам, в самом деле, не почитать учебники? Они же интересные, поверьте!

[Ascar]

venco в сообщении #341714 писал(а):

До $10^{15}$ есть только ещё один контрпример - 46912496118443.

опытным путем установленна связь между последовательностью A054723 и исключениями для нашего теста (для последовательности A175625)

другими словами между {исключениями в показателях степени чисел Марсена} и {нашими исключениями} имеет место быть какаято зависимость

расматривая второе известное исключение (наиденное venco)
$2*i+7=46912496118443$ => $i+3=23456248059221=(2^{23}-1)*2796203=(2^{46}-1)/3$
предположим что $46+1=47$ имеет место быть в последовательности A054723

почемубы не проверить остальные числа из последовательности A054723 по этому принципу
в итоге получил!!! новые исключения для последовательности A175625, по извесным элементам A054723

первый столбец элемент последовательности A054723
второй столбец исключение $2*i+7$ для последовательности A175625 и прицип получения по $i+3$

A054723      2*i+7 exception(A175625)
-----------------------------------------------------
47         46912496118443 (исключение наиденное venco) i+3=(2^46-1)/3
New find exception for A175625
59         192153584101141163 => i+3=(2^58-1)/3
83         3223802185639011132549803 => i+3=(2^82-1)/3
179         255415923477648143059724504525051530603123187030600363 => i+3=(2^178-1)/3
227         71893191112401706119112040232052348463032385126774859949609627331243 => i+3=(2^226-1)/3   
263         4940462474125491004739028693704017401739519345733997399016856917670960197970603 => i+3=(2^262-1)/3

[maxal]

Ascar в сообщении #341588 писал(а):

у меня просьба, если ваши (да и любого кто читает это сообщение) технические средства позволяют в разумные сроки наити следующие контр примеры по моему тесту, немогли бы вы выложить результаты

Контрпримерами являются, в частности, числа $\frac{2^k+1}3$, где $k$ пробегает элементы последовательности:

47, 59, 83, 107, 179, 227, 263, 359, 383, 467, 479, 503, 563, 587, 683, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2543, 2579, 2819, 2879, 2903, 2963, 2999, 3023, 3119, 3167, 3203, 3467, 3623, 3779, 3803, 3863, 3947, 4007, 4079, 4127, 4139, 4259, 4283, 4547, 4679, 4703, 4787, 4799, 4919, 4931, 5087, 5099, 5387, 5399, 5483, 5507, 5639, 5879, 5927, 5939, 6047, 6599, 6659, 6719, 6779, 6827, 6899, 6983, 7079, 7187, 7247, 7523, 7559, 7607, 7643, 7703, 7727, 7823, 8039, 8147, 8423, 8543, 8699, 8747, 8783, 8819, 8963, 9467, 9587, 9719, 9743, 9839, 9887, ...

Далеко не все они являются элементами A054723.

[Ascar]

maxal в сообщении #342656 писал(а):

Ascar в сообщении #341588 писал(а):

у меня просьба, если ваши (да и любого кто читает это сообщение) технические средства позволяют в разумные сроки наити следующие контр примеры по моему тесту, немогли бы вы выложить результаты

Контрпримерами являются, в частности, числа $\frac{2^k+1}3$, где $k$ пробегает элементы последовательности:

47, 59, 83, 107, 179, 227, 263, 359, 383, 467, 479, 503, 563, 587, 683, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2543, 2579, 2819, 2879, 2903, 2963, 2999, 3023, 3119, 3167, 3203, 3467, 3623, 3779, 3803, 3863, 3947, 4007, 4079, 4127, 4139, 4259, 4283, 4547, 4679, 4703, 4787, 4799, 4919, 4931, 5087, 5099, 5387, 5399, 5483, 5507, 5639, 5879, 5927, 5939, 6047, 6599, 6659, 6719, 6779, 6827, 6899, 6983, 7079, 7187, 7247, 7523, 7559, 7607, 7643, 7703, 7727, 7823, 8039, 8147, 8423, 8543, 8699, 8747, 8783, 8819, 8963, 9467, 9587, 9719, 9743, 9839, 9887, ...

Далеко не все они являются элементами A054723.

спасибо за анализ
а Вы целеноправленно рассматривали только простые числа, или проверяли все числа подряд ? :)
а то прям так и напрашивается - новый тест на простоту :) любое $k$ дающее контрпример последовательности A175625

пы сы вроде этой последовательности нет в OEIS.... ну и откуда ей там появится :)

[Ascar]

если добавить к этому тесту A175625
следующее условие

$(n-1)/2$ не имеет делителей вида $(2^{k}-1)$, где $k$ - целое и $1<(2^{k}-1)<(n-1)/2$ ; (1)

то исходя из сообщения venco о том что до $10^{15}$ есть только два исключения для последовательности A175625 и оба они не проходят предложенного условия (1) (т.е. $(n-1)/2$ для обоих исключений имеет делитель вида $(2^{k}-1)$), то мы имеем тест не имеющий исключений до $10^{15}$

причем первые элементы новой последовательности (A175625 + условие(1)) совпадают с последовательностью A005385
может ктонибудь проверит насколько глубоко они совпадают :)

[Ascar]

извините
4931
9719
и т.д.
не удовлетворяют этому правилу

$(n-1)/2$ на простоту проверять нельзя

[Ascar]

ктонибудь подскажите пожалуста
где почитать?
какие существуют методы факторизации "псевдопростых чисел по основанию 2" A001567 (кроме чисел Марсена)

нарисовался метод у меня, вдруг опять велосипед изобрел

[maxal]

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$ ищется аналогично вышесказанному.