Максимальные интервалы между взаимно простыми числами

[Yury_rsn]

Pphantom в сообщении #1537750 писал(а):

дождитесь какой-нибудь реакции от собеседников

Ок. Жду

[hitler]

Во-первых интервалы могут быть сколь угодно большими. Во-вторых, вычислять их мы не умеем, не находя всех интересующих нас простых чисел, поскольку разбросаны они довольно хаотично. А простые числа быстрее всего искать Быстрым Решетом Эратосфена за O(n)

[vicvolf]

hitler

(Оффтоп)

Зачем выбрали такой ник?

[Yury_rsn]

hitler в сообщении #1537921 писал(а):

Во-первых интервалы могут быть сколь угодно большими.

Интервалы для каждого праймориала ограничены соответствующим значением функции Якобсталя.
Или вы про другое?

Цитата:

Во-вторых, вычислять их мы не умеем, не находя всех интересующих нас простых чисел, поскольку разбросаны они довольно хаотично. А простые числа быстрее всего искать Быстрым Решетом Эратосфена за O(n)

Да, если искать интервалы напрямую, то от полного перебора не уйти.
И то, что в каждой строке надо перебрать не "p" значений, а "p-1", не намного упрощает ситуацию.

Но вот такая мысль.
Таблица цепочек для какого-то конкретного праймориала позволяет делать перебор в несколько приемов.
Посмотрите, пожалуйста, таблицу для 37#, d=66
https://docs.google.com/spreadsheets/d/ ... sp=sharing
- я вынес в отдельный файл этот случай. 37#

Если оставить числа (оранжевые) только в строках 5 и 7, а в ячейках с D6 по D13 удалить, то в ячейке F2 появится число 13. Это количество пустых столбцов на интервале, не вычеркнутых 5 и 7.
Я перебрал все варианты взаимных расположений пятерок и семерок (т.е., различные числа в ячейках D4 и D5). И только два варианта из них позволяют получить минимум F2=13
Две "ветки" - D4=1; D5=2 и D4=1; D5=3.

Теперь включим следующую строку. Перебираем значения в ячейке D6
Минимум F2=11 у нас достигается только при наборах D4=1; D5=2; D6=3 и D4=1; D5=2; D6=5
А для второй ветви возможен только один минимум - D4=1; D5=3; D6=9

В данном простом случае - 37#, мы легко найдем два известных варианта с помощью такого рода подходящих прикидок.

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

-- 07.11.2021, 00:08 --

И еще одно замечание - по случаю 37#
Две ветки имеют такие особенности:
И в одном, и в другом случае, интервалы Якобсталя "вместились" внутрь пятерок. Т.е., и самое левое число интервала, и самое правое делится на 5. Строка пятерок как бы осталась неподвижной при смещении всех строк. Столбцы 1, 4, 11, 14, 21.

Также, остался неподвижным столбец номер 13 - относительно пятерок. В нем может находиться любая свободная единица, но не попадают цепочечные числа.

Будут ли разветвления в следующих праймориалах обладать подобными особенностями?
Не понятно.

[vorvalm]

В интервале d = 282 среди цепочек нет свободных простых, но есть два,
у которых цепочка из 2-х вычетов, один их которых не свободен.
Эти числа не самые большие в модуле ПСВ и их можно считать
условно свободными.

[Yury_rsn]

vorvalm в сообщении #1538026 писал(а):

В интервале d=282 среди цепочек нет свободных простых, но есть два,
у которых цепочка из 2-х вычетов, один их которых не свободен.
Эти числа не самые большие в модуле ПСВ и их можно считать
условно свободными.

89 одним вычетом пересекается с 29 (цепочка из 4 вычетов).
97 одним вычетом пересекается с 5 (цепочка из 19 вычетов).

Их как-то можно поменять местами между собой (как это получается со свободными единицами)?
Я не пойму, как это можно сделать.

Положение любой цепочки, даже всего лишь из двух элементов, жестко детерминировано в таблице.
Если мы, допустим, поместим первое число 89 в столбец 6 (где сейчас расположено число 97), то у нас сразу освободится столбец 60 - там, где сейчас находится вторая 89-ка.

Чтобы его заполнить мы не сможем сдвинуть 97 на позицию 60, так как и у 97 второй вычет непредсказуемо уедет

upd
Увидел свою ошибку. Надо менять местами не те вычеты, которые под верхними цепочками, а те которые свободны. Тогда получается.
Единственное, за чем надо следить - чтобы при смещении строк, один из вычетов не попадал на ограничительный пустой столбец (в данном случае столбец номер 94).

[vorvalm]

Yury_rsn в сообщении #1538119 писал(а):

Положение любой цепочки, даже всего лишь из двух элементов, жестко детерминировано в таблице.
Если мы, допустим, поместим число первое число 89 в столбец 6 (где сейчас расположено число 97), то у нас сразу освободится столбец 60 - там, где сейчас находится вторая 89-ка.
Чтобы его заполнить мы не сможем сдвинуть 97 на позицию 60, так как и у 97 второй вычет непредсказуемо уедет

Несвободные вычеты цепочки при перемещении свободных могут занять
любое положение в интервале. Это не отразится на остальных цепочках.

[Yury_rsn]

vorvalm в сообщении #1538132 писал(а):

Несвободные вычеты цепочки при перемещении свободных могут занять
любое положение в интервале. Это не отразится на остальных цепочках.

Да, спасибо. Я уже увидел.

Значит, для случая n=27, d=282 разветвление не требуется. Количество различных интервалов совпадает с таблицей Циллера. Всего таких интервалов для 103# будет 4 шт.

Кстати, надо тогда посмотреть и другие праймориалы. Может еще где-то этот эффект срабатывает.

[Yury_rsn]

До 27 нигде не возникает условно свободных двоек.
Для n=28, 29 нижние строки - условно свободны.
Для n=30 - строка 71.

Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30

[vicvolf]

Yury_rsn в сообщении #1538160 писал(а):

Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30

Значит гипотеза не проходит.

[Yury_rsn]

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

Yury_rsn в сообщении #1538160 писал(а):

Пересчитал эти четыре случая. С таблицей Циллера совпало только для n=27 и 30

Значит гипотеза не проходит.

Наоборот.
Это означает, что в случаях 28 и 29, например, должно быть разветвление.
В таблице Циллера число больше, чем по свободным единицам

[vicvolf]

Я правильно понял, что неполный перебор при нахождении максимальных интервалов возможен только при наличии разветвлений? О наличии разветвлений в праймориале Вы узнаете только с использованием таблицы Циллера. А как находить максимальные интервалы для праймориалов больше, чем указаны в таблице Циллера?

[Yury_rsn]

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

Я правильно понял, что неполный перебор при нахождении максимальных интервалов возможен только при наличии разветвлений?

Наверное, надо еще раз сказать, что мы имеем в виду под "разветвлениями".
Пока что мы достоверно знаем только об одном разветвлениии. При 37# -
post1517825.html#p1517825

Разветвление при 37# означает, что для этого праймориала существуют две несовпадающие раскладки чисел по таблице вычетов. Их нельзя перевести друг в друга какой-то взаимной перестановкой расположения вычетов в столбцах между собой. Эта невозможность обуславливается наличием так называемых "цепочек" - это когда в строке вмещается два и больше вычетов. В приведенных выше примерах цепочки образуются в строках 5, 7, 11, 13, 17, 19, 23. И как видно, в каждом из примеров, числа из этих цепочек расположены в разных столбцах, кроме пятерок.

А одиночные числа в строке (свободные единицы) - находятся в строках 29, 31, 37.
Если мы поменяем мысленно местами (т.е., сдвинем их в другие столбцы) эти три числа, то это будут другие интервалы, но "конструкция" их останется прежней - самое левое число интервала будет кратно 5, второе слева - кратно 7, третье слева - кратно 23... И так далее, за исключением столбцов 10, 13, 15.
Сейчас в этих столбцах находятся соответственно числа 37, 31, 29.
И если мы расположим в этих столбцах 31,37,29 или 29,37,31 или 29,31,37 и т.д., то полученный интервал лишь сместится по числовой оси, но на вид останется таким же самым. Следовательно, всего интервалов такого вида для 37# будет 3!, т.е., 6 шт. А также столько же будет "зеркальных" - еще 6 шт.
Но как вычислил Дмитрий, на самом деле, для 37# имеется всего не 12, а 24 различных интервалов длины d=66.

Как выяснилось, это означает, что существует еще одна "ветка". Интервалы, где цепочки располагаются совершенно по-другому. Эти интервалы очень похожи на первую ветку. Цепочки есть в строках с 5 до 23, а свободные единицы тоже располагаются в строках 39,31,37. Но только в других столбцах.
И этих интервалов точно по такой же логике всего будет 12.
Итого, суммарно - 24.

Цитата:

О наличии разветвлений в праймориале Вы узнаете только с использованием таблицы Циллера.

Да, таблица Циллера подсказывает гипотезу, что в некоторых строках должны возникнуть несколько веток. Аналогично 37#.
Но мы пока даже их найти не можем. Слишком большие вычисления требуются.

Цитата:

А как находить максимальные интервалы для праймориалов больше, чем указаны в таблице Циллера?

Пока никак. Нужны "большие" компьютеры.

[vicvolf]

У Гербича таблица максимальных интервалов ПСВ до праймориала 57-ого по порядку простого числа.

Однако Dmitriy40 в другой теме считал максимальные интервалы для ПСВ гораздо больших праймориалов. Полным перебором это не сделаешь.

Интересно, какие свойства ПСВ он использовал?

[Dmitriy40]

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