Кортежи из простых чисел

[Cantata]

Ende
Выделено из темы «Как писать быстрые программы»

Здравствуйте! Попробовала с помощью своей трапеции поискать кортежи. Проверьте, пожалуйста:

Число в колонке «Найдено» это не количество кортежей,
а общее количество простых чисел, которые попали в поисковое окно шириной MAX_SPAN, равное 150 для конкретного k.

 Поиск коротких кортежей длины 7
 Масштаб: ~3 цифры | k ∈ [10,100]
Идет поиск...
------------------------------------------------------------
 k  | Найдено | Размах | Первый | Полный кортеж (первые 7)
------------------------------------------------------------
  ...проверка k=10
10  | 26       | 42      | 317   | [317, 331, 337, 347, 349, 353, 359]
11  | 26       | 36      | 331   | [331, 337, 347, 349, 353, 359, 367]
12  | 26       | 32      | 347   | [347, 349, 353, 359, 367, 373, 379]
13  | 25       | 34      | 367   | [367, 373, 379, 383, 389, 397, 401]
14  | 25       | 40      | 379   | [379, 383, 389, 397, 401, 409, 419]
15  | 23       | 42      | 389   | [389, 397, 401, 409, 419, 421, 431]
16  | 23       | 38      | 401   | [401, 409, 419, 421, 431, 433, 439]
17  | 23       | 30      | 419   | [419, 421, 431, 433, 439, 443, 449]
18  | 23       | 30      | 431   | [431, 433, 439, 443, 449, 457, 461]
19  | 23       | 28      | 439   | [439, 443, 449, 457, 461, 463, 467]
  ...проверка k=20
20  | 22       | 38      | 449   | [449, 457, 461, 463, 467, 479, 487]
21  | 23       | 38      | 461   | [461, 463, 467, 479, 487, 491, 499]
22  | 23       | 42      | 479   | [479, 487, 491, 499, 503, 509, 521]
23  | 23       | 36      | 487   | [487, 491, 499, 503, 509, 521, 523]
24  | 23       | 50      | 491   | [491, 499, 503, 509, 521, 523, 541]
25  | 23       | 54      | 503   | [503, 509, 521, 523, 541, 547, 557]
26  | 24       | 48      | 521   | [521, 523, 541, 547, 557, 563, 569]
27  | 24       | 48      | 521   | [521, 523, 541, 547, 557, 563, 569]
28  | 24       | 36      | 541   | [541, 547, 557, 563, 569, 571, 577]
29  | 25       | 36      | 541   | [541, 547, 557, 563, 569, 571, 577]
  ...проверка k=30
30  | 24       | 36      | 557   | [557, 563, 569, 571, 577, 587, 593]
31  | 25       | 36      | 557   | [557, 563, 569, 571, 577, 587, 593]
32  | 24       | 32      | 569   | [569, 571, 577, 587, 593, 599, 601]
33  | 23       | 36      | 577   | [577, 587, 593, 599, 601, 607, 613]
34  | 24       | 30      | 587   | [587, 593, 599, 601, 607, 613, 617]
35  | 25       | 26      | 593   | [593, 599, 601, 607, 613, 617, 619]
36  | 24       | 40      | 601   | [601, 607, 613, 617, 619, 631, 641]
37  | 23       | 34      | 613   | [613, 617, 619, 631, 641, 643, 647]
38  | 23       | 36      | 617   | [617, 619, 631, 641, 643, 647, 653]
39  | 23       | 30      | 631   | [631, 641, 643, 647, 653, 659, 661]
....
  ...проверка k=100
100  | 23       | 30      | 1009   | [1009, 1013, 1019, 1021, 1031, 1033, 1039]
------------------------------------------------------------
Всего найдено: 91

-- добавлено через 56 секунд --

Тут подлиннее кортежи нашлись:

Поиск кортежей длины 15
 Масштаб: 50 цифр | k ∈ [10,100]
 Идет поиск...
------------------------------------------------------------
 k  | Найдено | Размах 15-ки | Последние 8 цифр первого
------------------------------------------------------------
  ...проверка k=10
  ...проверка k=20
  ...проверка k=30
  ...проверка k=40
  ...проверка k=50
  ...проверка k=60
62  | 17       | 728          | 12202193
  ...проверка k=70
71  | 15       | 960          | 40156103
76  | 15       | 862          | 85046621
  ...проверка k=80
  ...проверка k=90
  ...проверка k=100
------------------------------------------------------------
 Всего найдено окон с >=15 простыми: 3

[Dmitriy40]

Cantata
Сформулируйте пожалуйста что за кортежи Вы искали (и нашли)? Т.е. каким условиям должны удовлетворять найденные кортежи? Условия полностью пожалуйста.

[Cantata]

Dmitriy40
Пока у меня простые кортежи, которые собраны исходя из их плотности на небольшом диапазоне чисел. Чат бот заверил, что такие кортежи тоже имеют место быть.

Я бы хотела поискать кортежи по всём необходимым параметрам, только заблудилась в количестве страниц и данных.

Где можно кратко всю необходимую информацию прочитать, чтобы провести свои тесты?

Ещё сложность в том, что когда захожу в аккаунт, половина страниц становится недоступной.

[Dmitriy40]

Cantata в сообщении #1725255 писал(а):

Пока у меня простые кортежи, которые собраны исходя из их плотности на небольшом диапазоне чисел.

Понятней не стало.
Что именно Вы считаете плотностью? Какая она должна быть чтобы Вы посчитали это кортежем?
И нет, это не риторические вопросы, правильных (в любом смысле) ответов на них может быть больше одного.

Cantata в сообщении #1725255 писал(а):

Где можно кратко всю необходимую информацию прочитать, чтобы провести свои тесты?

Какую информацию? Кортежей, в том числе из простых чисел, множество вариантов, Вас какие интересуют?
Бывают например кортежи максимальной плотности, их примеры с текущими рекордами собраны например здесь: https://pzktupel.de/Top10.php На этом же сайте много примеров других кортежей.
Ещё один сайт про множество кортежей и вариантов простых чисел: https://t5k.org/
Но на них кажется нет тех кортежей, которые мы искали, в том числе здесь на форуме (только поиск по слову кортеж в названии темы, так то тем ещё больше):
search.php?keywords=%D0%BA%D0%BE%D1%80%D1%82%D0%B5%D0%B6*&terms=all&author=&sc=1&sf=titleonly&sk=t&sd=d&sr=topics&st=0&ch=300&t=0&submit=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA
Особенно рекомендую topic100750.html и topic156968.html

Cantata в сообщении #1725255 писал(а):

Ещё сложность в том, что когда захожу в аккаунт, половина страниц становится недоступной.

Про это уже сразу несколько тем в Работе форума наплодили:
topic162853.html
topic162481.html
topic160679.html
topic161969.html
topic161589.html
В первых трёх есть и способы обхода ограничений.

-- добавлено через 1 минуту --

PS. Как вопрос прояснится - попрошу модератора вырезать обсуждение в отдельную тему с подходящим названием или в существующую тему если подойдёт.

[Yadryara]

Cantata
Да, это Вы большая молодец, что пытаетесь разобраться.

Если прога на PARI, то я вроде знаю что посоветовать, а если Пайтон, то не очень охота вникать.

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

Для знакомства с темой — вроде самое то. От простого к сложному.

Для симметричных кортежей из последовательных простых чисел нынче вроде нет интересных задач. 21-ку найти ну о-о-о-чень сложно.

А вот кортежи с одинаковым количеством делителей более сложная, но зато и более интересная тема...

[Dmitriy40]

Yadryara в сообщении #1725261 писал(а):

Для кортежей из простых чисел нынче вроде нет интересных задач. 21-ку найти ну о-о-о-чень сложно.

Совсем не сложно - она давно найдена, в январе 2015г: https://pzktupel.de/KTHIST/kt021.php
Или говорите точнее какую именно 21-ку Вы подразумеваете, не все в курсе ваших сокращений и умолчаний.

[Yadryara]

Dmitriy40 в сообщении #1725263 писал(а):

Или говорите точнее какую именно 21-ку Вы подразумеваете

Да, сам подумал, что надо уточнить и уже уточнил, поправил пост. Но быстро не получилось — доступ на форум весьма затруднён.

А сейчас ещё и подчеркну:

Yadryara в сообщении #1725261 писал(а):

Для симметричных кортежей из последовательных простых чисел нынче вроде нет интересных задач. 21-ку найти ну о-о-о-чень сложно.

[Dmitriy40]

Yadryara в сообщении #1725261 писал(а):

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

Исходя из предыдущих тем, она скорее пытается подобрать "формулу" для начала брутфорса, чтобы кортежи находились почаще чем при случайном выборе начального числа. Про паттерны речи вроде не идёт.
Хотя что именно подразумевает под кортежем непонятно.

Yadryara в сообщении #1725261 писал(а):

Для симметричных кортежей из последовательных простых чисел нынче вроде нет интересных задач. 21-ку найти ну о-о-о-чень сложно.

Есть, например: https://www.pzktupel.de/CPAP/mini.php
И есть интересные варианты для несимметричных или для непоследовательных. Много разных. Например:
https://www.pzktupel.de/BiTwin/BiTwin.php
https://www.pzktupel.de/CC/cc.php
https://www.pzktupel.de/PAP/aprecords.php (4 разных варианта)
Но лёгкие тоже уже нашли, это да.

[Cantata]

Dmitriy40 в сообщении #1725260 писал(а):

Что именно Вы считаете плотностью? Какая она должна быть чтобы Вы посчитали это кортежем?
И нет, это не риторические вопросы, правильных (в любом смысле) ответов на них может быть больше одного.

Кортежи имеют небольшой размах (26–54 для длины 7) и формируются методом брутфорса.
Чат бот за основной критерий отбора данных чисел в кортеж, как я понимаю, взял только локальное превышение плотности относительно асимптотической оценки. Никаких специальных условий на разности или симметрию задано не было.

Попробую задать условия, если будет что-то интересное, напишу.

Dmitriy40 в сообщении #1725260 писал(а):

Какую информацию? Кортежей, в том числе из простых чисел, множество вариантов, Вас какие интересуют?

Благодарю за сайты! Море информации, пока глаза разбегаются, правда не все сайты открылись но и этого предостаточно :)

-- добавлено через 4 минуты --

Yadryara в сообщении #1725261 писал(а):

Да, это Вы большая молодец, что пытаетесь разобраться.

Спасибо, я только потестить алгоритм хотела. Хотя, конечно, он только начальный интервал дает.

Yadryara в сообщении #1725261 писал(а):

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

Да, так и есть, пока вникаю в саму тему в основном с помощью чат бота - на нём вся ответственность за методику поиска :)

-- добавлено через 2 минуты --

Dmitriy40 в сообщении #1725268 писал(а):

Есть, например: https://www.pzktupel.de/CPAP/mini.php
И есть интересные варианты для несимметричных или для непоследовательных. Много разных. Например: https://www.pzktupel.de/BiTwin/BiTwin.php https://www.pzktupel.de/CC/cc.php https://www.pzktupel.de/PAP/aprecords.php (4 разных варианта)
Но лёгкие тоже уже нашли, это да.

Спасибо! Что бы тогда попробовать поискать для начала?

[Dmitriy40]

Cantata в сообщении #1725294 писал(а):

Спасибо! Что бы тогда попробовать поискать для начала?

Если чисто наудачу, не запуская вычисления на месяцы и годы, то поискать улучшения вот этих цепочек длиной 7 (и более): https://www.pzktupel.de/CPAP/mini.php (CPAP-7 - 7 последовательных простых с шагом 210).
Найти гарантированно минимальную вряд ли получится (ведь надо доказывать что наименьшая), а вот улучшить текущие рекорды (т.е. уменьшить известные решения) почему бы нет. Тем более там оценка для CPAP-7 на два порядка (раз в 100) меньше текущего рекорда, так что простор для поиска есть. А прогресса нет уже почти 6 лет.
Но шанс наугад найти улучшение - очень невелик.
Зато там можно применять много разных оптимизаций, не только ускоряющих поиск, но и сужающих пространство поиска (например сделать некоторые числа между простыми гарантированно составными выбором остатков от деления на малые простые).
Поиск по паттерну там малоэффективен так как проблема не в нахождении цепочки из семи простых (таких цепочек триллионы, только до 1000 они начинаются с 47, 179, 199, 409, 619, 829, 881), а чтобы между ними не было других простых, вот в этом и проблема.

[Yadryara]

Cantata в сообщении #1725294 писал(а):

Кортежи имеют небольшой размах (26–54 для длины 7) и формируются методом брутфорса.
Чат бот за основной критерий отбора данных чисел в кортеж, как я понимаю, взял только локальное превышение плотности относительно асимптотической оценки.

Так и понял что вы самые плотные ищете. Мы тоже долгое время искали. Знаменитый кортеж из последовательных простых чисел 19-252, который нашли, как раз самый плотный из симметричных и с максимальной длиной.

Dmitriy40 в сообщении #1725296 писал(а):

7 последовательных простых с шагом 210).

Как понимаю, Дмитрий предлагает наоборот искать весьма разреженные кортежи, с огромными гэпами 210. То есть по паттерну [ 0, 210, 420, 630, 840, 1050, 1260 ].

Насколько помню (искать по форуму почти не могу), самый популярный гэп для симметричных нечётных кортежей сначала был 6, а затем на больших высотах уже 30.

У меня форум почти перестал открываться . Делаю по 10-20 попыток, чтобы открыть одну-единственную страницу. Вот и сейчас не уверен, что удастся отправить.

У меня нет проводного Интернета, только мобильный. Если пропаду, и не отвечу кому-то, я не виноват. Кстати, почта-то должна работать, кто её знает, можете написать, буду чаще её проверять.

Я понимаю что это надо не здесь писать. А в "Работе форума", там куча однотипных тем о проблемах с доступом. Но у меня-то не открывается уже полдня...

Ещё попробую, если получится напишу туда.

[Dmitriy40]

Yadryara в сообщении #1725300 писал(а):

Как понимаю, Дмитрий предлагает наоборот искать весьма разреженные кортежи, с огромными гэпами 210. То есть по паттерну [ 0, 210, 420, 630, 840, 1050, 1260 ].

Да.
Потому что компактными и так много занимаются на серьёзных мощностях, а этими то ли не занимаются вообще, то ли тыкают наугад. За 2018 год три улучшения CPAP-7 аж в 31 раза, а потом как отрезало 5 лет. Плюс оценка перспективы ещё раз в 100 улучшить.
Ну и там простор для разных оптимизаций, есть где голову (или чатбота) поломать.
И есть шанс даже случайно найти улучшение рекорда. Маленький, но заметнее чем с другими задачами.

Ещё можно поискать некоторые варианты по ссылке где было 4 варианта цепочек, в частности с минимальным диаметром (minimal difference) и с минимальным началом (minimal start), там тоже относительно реально даже и случайно найти улучшение рекордов. Например я нашёл улучшения всего за сутки счёта (правда в 64 потока) и за полторы недели, дальше же прогресс остановился на полгода.

[Cantata]

Спасибо, попробую поискать.
Скорее всего смогу написать результаты только через неделю.

[Yadryara]

Yadryara в сообщении #1725300 писал(а):

Знаменитый кортеж из последовательных простых чисел 19-252, который нашли, как раз самый плотный из симметричных и с максимальной длиной.

Забыл уточнить, но попробую исправиться. Я имел в виду кортежи нечётных длин, которыми долгое время и занимались. Поэтому и говорил про 19-ку и 21-ку:

Yadryara в сообщении #1725261 писал(а):

21-ку найти ну о-о-о-чень сложно.

Насколько помню, 19-к известно всего лишь 4 штуки, а 21-ки пока что ни одной неизвестно, не то что с минимальным, а вообще с каким-либо диаметром.

А у чётных кортежей того же класса (симметричных из последовательных простых чисел) своя песня. Вроде бы даже кортеж длиной 28 был найден. Если кому интересно смотрите, например, в проекте SPT или здесь на форуме. Ссылки, если угодно, попробую поискать.