Получение множества простых чисел

[maravan]

Всем привет!

Хотел поинтересоваться, имеется ли ценность (практическая и теоретическая) нахождения простых чисел по следующему алгоритму:

Имеем:
$p_{1}...p_{n}, n \in \mathbb Z, $p_{1}...p_{n} \in \mathbb P$.

Ищем все простые числа для интервала: $(p_{i}, p_{i}^2), i \in \mathbb Z$.

1. Берем известные, последовательные простые числа $p_{1}...p_{n}$;
2. Составляем множество P разностей произведения $\prod \limits_{i=1}^n p_{i}^{a_{i}} - \prod \limits_{i=1}^n p_{i}^{b_{i}}$, где $a_{i},b_{i} \in \mathbb Z \cup [0]$. $a_{i},b_{i}$ на каждом шаге произведения выбираются таким образом, чтобы получить уникальное множество.

Все элементы множества P будут простыми числами.

Пример:

Ищем все простые числа до 25, имея известный набор 2,3,5
1. 2,3,5
2.

$P_{1} = 2^1 3^0 5^1-2^0 3^1 5^0 = 7$
$P_{2} = 2^2 3^0 5^1-2^0 3^2 5^0 = 11$
$P_{3} = 2^0 3^1 5^1-2^1 3^0 5^0 = 13$
$P_{4} = 2^2 3^0 5^1-2^0 3^1 5^0 = 17$
$P_{5} = 2^6 3^0 5^0-2^0 3^2 5^1 = 19$
$P_{6} = 2^1 3^0 5^2-2^0 3^3 5^0 = 23$

[Sonic86]

Нет, это баян. (т.е. я не скажу, что я метод видел где-то в книгах, но придумывал сам, хотя я почему-то тогда возводить простые в степени не додумался)
Во-первых, не факт, что Вы получите так все простые из интервала $(p_j;p_j^2)$. Если бы степеней не было, то 19 нельзя получить. Думаю, что если от начала натуральных чисел уйти подальше, то можно и для этого случая найти исключение.
Ну или попробуйте доказать. Вдруг я неправ.
Во-вторых, с ростом $n$ колебания этих разностей произведений будут очень сильные - Вы будете все чаще выходить за пределы $(p_j;p_j^2)$. И тогда не факт, что получаемые числа будут простыми.

[Someone]

Б.А.Кордемский. Математическая смекалка. Государственное издательство технико-теоретической литературы. Москва, 1957.

Это четвёртое издание. Книга предназначена для школьников 10-11 лет (в то время - 3-4 класс), а также в какой-то мере и для более старших читателей. Предлагаемый метод излагается в книге в главе четырнадцатой, пункт 359, который называется "Ещё один способ получения простых чисел". Обоснование метода предлагается читателю в качестве нетрудного упражнения.

[Sonic86]

Someone в сообщении #524057 писал(а):

"Ещё один способ получения простых чисел". Обоснование метода предлагается читателю в качестве нетрудного упражнения.

Посмотрел, там написано

Цитата:

Если сумма или разность этих произведений даст число $N$, меньшее чем квадрат $n+1$-го числа, то $N$ - простое число

Т.е. не факт, что все такие произведения простые без этого ограничения.

[maravan]

2 Sonic86:

Я не говорю, что все разности произведения будут простыми числами. Я говорю про интервал $(p_{i}, p_{i}^2)$, даже (по Б.А.Кордемскому, $(p_{i}, p_{i+1}^2)$) , что если разность произведений попадает в этот интервал, то результат - простое число=).

2 Someone:

О! Спасибо за ссылку, в принципе, я так и думал, что подобное уже есть=) Скачал книжку - посмотрел, действительно доказательство достаточно простое=)


Всем спасибо, всех с Рождеством!

[vorvalm]

Предлагаемая формула определения простых чисел является частным случаем общей формулы для вычетов ПСВ (приведенная система вычeтов)по модулю $M(p)=\prod_2^p p ,\quad p\mid M.$

$ a_x=\mid \prod_{p_s}p_s^{\alpha_s}\pm \prod_{p_t}p_t^{\beta_t}\mid<M(p_r)=\prod_{p_s}p_s\cdot\prod_{p_t}p_t.$ $,\quad \alpha_s,\beta_t\in\mathbb{N}.$

При условии $1<a_x<p^2_{r+1} $ , все вычеты будут простыми.
Пример
При $M=30$
$6-5=1,\;12-5=7,\;18-5=13,\;24-5=19$
$6+5=11,\;12+5=17,\;18+5=23,\;24+5=29.$