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

[serval]

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

у Вас хочу спросить: "А вы о каких последовательностях спрашиваете?"

Я спрашиваю о двух последовательностях из правых частей сравнений:
$A\equiv 2n \ (mod \ 2n-4)$
$A\equiv 6n \ (mod \ 2n-12)$
и так далее.
$2n,\ 6n, \ \ldots$ - что дальше?
$2n-4,\ 2n-12, \ \ldots$ - что дальше?
Приведите вид общего члена каждой из последовательностей. Или дайте еще по три следующих члена - я попробую обобщить, а вы проверите.
И распишите, пожалуйста, явно - что такое $RN$.

[serval]

И это всё?

[livan]

Извините если что не так (ну типа не там спрашиваю).
Есть формула последовательности - она выдает первые 18 простых чисел, потом начинает врать.
Хотел узнать насколько интересное открытие (правда как-то громко звучит).
Показал одному математику - он сказал ерунда - таких много.
Искал в Инете что-нибудь подобное - ничего.
Неужели правда ничего интересного?

[gris]

Вы знаете, это зависит от простоты формулы.
Обычный интерполяционный многочлен по сами-понимаете-каким точкам может дать формулу для какого угодно количества первых простых чисел. Но он будет очень громоздким. Если же Вам удастся найти простую, компактную формулу, то она может представлять интерес.

[Someone]

Многочлен Эйлера $x_n=n^2-n+41$ даёт простые числа для $n=1,2,3,\ldots,40$.
http://www.ega-math.narod.ru/Quant/Primes.htm

[Sonic86]

livan писал(а):

Извините если что не так (ну типа не там спрашиваю).
Есть формула последовательности - она выдает первые 18 простых чисел, потом начинает врать.
Хотел узнать насколько интересное открытие (правда как-то громко звучит).

ну $a_n=6n-1$ тоже выдает простые довольно часто.
Вы попробуйте доказать, что Ваша формула выдает бесконечное множество простых, пусть даже не подряд (если она действительно выдает). Вот это может быть кого-то удивит.

[venco]

Sonic86 в сообщении #331532 писал(а):

livan писал(а):

Извините если что не так (ну типа не там спрашиваю).
Есть формула последовательности - она выдает первые 18 простых чисел, потом начинает врать.
Хотел узнать насколько интересное открытие (правда как-то громко звучит).

ну $a_n=6n-1$ тоже выдает простые довольно часто.
Вы попробуйте доказать, что Ваша формула выдает бесконечное множество простых, пусть даже не подряд (если она действительно выдает). Вот это может быть кого-то удивит.

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

[gris]

Особенно прогрессия $a_i=i$

[Sonic86]

venco писал(а):

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

Я не про арифметическую прогрессию, а про его формулу. Думаю, что она отличается от арифметической прогрессии.

Кстати: верно ли, что для любого $n$ существуют $a,b$ такие, что прогрессия $ak+b$ принимает подряд $n$ простых чисел?

[livan]

Спасибо всем за ответ.
У меня получилась не арифметическая прогрессия, а рекуррентная последовательность.
Причем, она работает (как мне кажется) и на других участках.
На данный момент серьезно посидеть не удается, завал на работе.
Как что-нибудь, через пару ночей, отпишусь поподробней.

[Sonic86]

livan писал(а):

У меня получилась не арифметическая прогрессия, а рекуррентная последовательность.

Хоть не линейная рекуррентная? А то соотношения $x_n=a_1x_{n-1}+...+a_mx_{n-m}$ в самом простом случае равносильны $x_n=C_1b_1^n+...+C_mb_m^n$, но уже в случае $m=2$ имеем 2 типа чисел $x_n=(n+1)^p-n^p$ и $x_n=a^{2^n}+b^{2^n}$, частные случаи соответственно - числа Мерсенна и Ферма, так люди до сих пор думают...

[RIP]

(Оффтоп)

Sonic86 в сообщении #331896 писал(а):

Кстати: верно ли, что для любого $n$ существуют $a,b$ такие, что прогрессия $ak+b$ принимает подряд $n$ простых чисел?

Да. Теорема Грина--Тао.

[Skipper]

Почитал тему...
SerjeyMinsk, вы даже не представляете, насколько вы далеки от всего того, что здесь пишете.
Знаний - абсолютный ноль. Т.е. знаний у вас - ни в программировании нету, ни в теории алгоритмов (если даже не знаете ВАЖНЕЙШИЕ понятия типа отличие экспоненциальных алгоритмов от полиномиальных!!! а это следовало из ваших сообщений), ни даже не то что в высшей математике... Знаний нету даже тех, что у меня были в 6-м классе средней школы - в обычной математике! Поразился, от вашего вопроса - типа - как так... "10 в 10-й степени считает быстро, почему 10 в 100-й степени будет дольше считать чем время существования Вселенной?.. Ведь только один ноль добавился" Ну я уверен, многие были под столом от этого... Но стало понятно, что вы даже систему десятичного счисления, и понятие что такое СТЕПЕНЬ числа до конца не представляете. Не представляете, почему если число возводить в большую степень - оно становится таким огромным...

Вам надо начать со школьного курса, проштудировать школьную математику, потом изучить высшую математику, теорию алгоритмов хотя бы, а потом еще предметную область - про факторизацию, простоту чисел и т.д. Иначе ничего лучше, чем модификацию решета Эратосфена (а ASSA именно это и представляет) - вы не придумаете.

Не в обиду будь сказано, но я прав на сто процентов. Спуститесь на землю, и займитесь лучше более полезным для вас делом - тем, в котором вы разбираетесь. А ваши наивные цитаты типа

Цитата:

Всё равно Assa надежней считает! И математических операций меньше как ни крути. Не знаю как там сложности алгоритмов по RAM или в битовых. Но это ГРАНИТ НАХОЖДЕНИЯ ПРОСТЫХ ЧИСЕЛ!
Заявит еще в науке, не сомневайтесь!

ничего кроме смеха у людей не вызывают. (И ваше желание чтобы вам побольше бабла заплатили за ваш Assa :)

[SerjeyMinsk]

Skipper, так я-ж только об этом и говорю. Не знаю вообще ничего из вашей математики, вашего программирования, ваших теорий алгоритмов. Я даже такой "ноль", что не только я, но и Вы себе представить не можете. Я вообще ничего не знаю.
А Вы мне можете привести доказательство того, что ASSA является модификацией решета Эратосфена? Не лозунгами, не болтовней, не чем-то иным, а строгим математическим доказательством. Я так понял Вы это легко можете сделать судя по тому, что Вы уж наверняка знакомы с Высшей математикой о которой Вы говорите.
И поставим точку в этой ветке.

[Skipper]

SerjeyMinsk, я не вижу смысла приводить такое строгое доказательство, тем более понятие "модификация" растяжимое, или так сказать, относительное. Кому-то кажется модификацией, а кому-то - чем-то новым.

Главное не это.
Главное то, что даже если вы в ASSA видите что-то новое, и оно будет работать на компьютере для определенных длинных чисел
100000000000000000000 лет (больше чем Вселенная существует),
и это вам все пытаются доказать уже давно,
а лучшие алгоритмы для этих же чисел работают на компьютере пару часов ,
то просто очевидно, что ASSA столь же неприменимо для больших чисел, как и решето Эратосфена! И нет смысла доказывать, модификация это или нет - важно оценить трудоемкость вашего алгоритма. И это уже многие здесь оценили. Не верите - вбейте длинные числа, какие вам предлагали, и ждите, пока они будут обработаны. Тогда поймете сами. А работа с малыми числами, поверьте, никого не интересует. Людям нужны длинные, большие простые числа.

Что нужно изучить, чтобы разбираться в этой области, я подсказал.
Тогда может, через 5 лет вы в самом деле, предложите какой-нибудь стоящий алгоритм.