Решето для нахождения простых чисел близнецов

[yk2ru]

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

Все пары простых-близнецов, кроме (3, 5), имеют вид $6n\pm 1$. Методом решета будут находиться эти числа $n$.
1. Выписать подряд все числа от 1 до некоторого числа $N$.
2. Взять первое число и получить числа p = $6n\pm 1$, для первого числа это числа $(5,7)$.
3. Зачеркнуть в списке числа от 6 до $N$ считая шагами по p от $1$ (это будут числа $6, 11, 16$, …) при $p = 5$ и соответственно ($8, 15, 22$, …) при $p = 7$.
4. Зачеркнуть в списке числа от 4 до $N$ считая шагами по p от ${-1}$ (это будут числа $4, 9, 14$, …) при $p = 5$ и соответственно ($6, 13, 20$, …) при $p = 7$.
Для следующего числа $2$ числа $p$ это $(11,12)$.
Третий и четвертый шаги соответственно такие:
3. Зачеркнуть в списке числа от 13 до $N$ считая шагами по p от $2$ (это будут числа $13, 24, 35$, …) при $p = 11$ и соответственно ($15, 28, 31$, …) при $p = 13$.
4. Зачеркнуть в списке числа от 9 до $N$ считая шагами по p от ${-2}$ (это будут числа $9, 20, 21$, …) при $p = 11$ и соответственно ($11, 24, 37$, …) при $p = 13$.
Повторять шаги 3 и 4 со следующими числами, пока возможно.
Все незачеркнутые числа в списке дают простые числа близнецы по формуле $6n\pm 1$.

Первое зачеркнутое число будет $4 = -1 + 5$ и значит из четверки по формуле $6n\pm 1$ не получить пару простых чисел близнецов, одно из чисел $25$ соответственно делится только на $5$.
Следующее число $5$ не перечеркивается шагами три и четыре и дает простые числа близнецы $(29,31)$.
Число $6 = 1 + 5$ и также $6 = -1 + 7$, значит одно из чисел вида $6n\pm 1$ делится на пять и на семь. Это число $35$.
Число $8 = -1 + 7$ другим способом не перечеркивается в списке, и значит одно из чисел 49 делится только на 7.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

Утверждение, цель алгоритма?

На данный момент не виден предмет дискуссии.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»

[Dmitriy40]

Вряд ли пригодится: там речь шла про тысяче- и более значные числа, что решету просто недоступно, а все близнецы до нескольких (десятков) миллиардов проще получить обычным решетом за секунды.
Возможно этот алгоритм имеет преимущество перед обычным решетом, но оно может наступить лишь где-то у триллионов, потому что до этого данный алгоритм слишком сложен по сравнению с обычным решетом и потому больше накладных расходов. А после скажем $10^{20}$ любое решето, и обычное и это, слишком медленно и накладно по памяти. Но числа (и простые близнецы тоже) в диапазоне $10^{12}\ldots 10^{20}$ малоинтересны.
Впрочем возможно нижняя граница и до миллиардов спустится, надо проверять, но там и обычное решето занимает секунды и зачем его ещё оптимизировать непонятно.
В общем интерес может быть скорее теоретическим, как метод получения именно простых близнецов.

[yk2ru]

Упрощение алгоритма:
Шаги с шагом $p=6n \pm 1$ делать от нуля. На очередном шаге, получив число $r = kp$, перечеркивать равноотстоящие от него два числа $r \pm n$. Так что алгоритм совсем не сложный.

[vicvolf]

yk2ru в сообщении #1524398 писал(а):

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

А какая цель? Есть решето Бруна, которое используется для оценки сверху количества простых близнецов. А у Вас?

[yk2ru]

vicvolf в сообщении #1524448 писал(а):

А какая цель?

Точно такая же, как и у решета Эратосфена. Способ получения простых чисел, в данном случае не всех, а близнецов, начиная с $(5,7)$. Какая цель могла быть у решета Эратосфена, кроме того, что это алгоритм для нахождения простых чисел на заданном числовом отрезке?

[vicvolf]

yk2ru в сообщении #1524466 писал(а):

vicvolf в сообщении #1524448 писал(а):

А какая цель?

Точно такая же, как и у решета Эратосфена. Способ получения простых чисел, в данном случае не всех, а близнецов, начиная с $(5,7)$. Какая цель могла быть у решета Эратосфена, кроме того, что это алгоритм для нахождения простых чисел на заданном числовом отрезке?

Так Эратосфен придумал свое решето для получения простых чисел, когда других не было. А Вы придумали свой алгоритм для получения простых близнецов, когда таких алгоритмов уже много. Я упомянул один. Прежде чем придумывать новый алгоритм надо проанализировать недостатки других. Может старые алгоритмы закрывают все требуемые ниши. Если нет, то чем Ваш алгоритм лучше?

[yk2ru]

vicvolf в сообщении #1524487 писал(а):

Прежде чем придумывать новый алгоритм надо проанализировать недостатки других.

Ну и зачем же разные люди (известные математики также) придумывали различные способы доказательства бесконечности простых чисел, можете ли вы сказать?
Девятнадцать доказательств теоремы Евклида:
http://kvant.mccme.ru/pdf/2001/01/kv0101evnin.pdf
А чтобы сравнить на лучше или хуже, то нужно запрограммировать и сравнивать, предварительно изучив разные существующие способы.

[Someone]

Двадцать наибольших известных пар простых близнецов.
Это просто чтобы автор нового решета посмотрел, какие простые близнецы интересны хотя бы любителям.

[yk2ru]

Знаком с сайтом price.utm.edu достаточно давно. Проекты по нахождению максимальных простых чисел, это своего рода тоже решето. Берут например для чисел Мерсенна большие числа простых показателей и запускают тест Люка - Лемера. За счет огромного количества добровольцев, участвующих в проекте, иногда получают подтверждение простоты для числа Мерсенна с очередным показателем.

[Dmitriy40]

В общем интерес скорее спортивный, ещё один метод получения небольших простых близнецов. Практического смысла пока не видно.

[Someone]

yk2ru в сообщении #1524548 писал(а):

Проекты по нахождению максимальных простых чисел, это своего рода тоже решето.

Когда каждое число проверяется отдельно, независимо от остальных — это не решето.