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

[vicvolf]

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

Цитата:

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

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

Или искать алгоритмы неполного перебора вариантов. Об одном таком алгоритме я хотел сказать.

При переходе от ПСВ$p_{r-1}\#$ к ПСВ$p_r\#$ удаляются вычеты $p^2_r,p_rp_{r+1},...$, поэтому именно здесь появляются новые интервалы между вычетами для ПСВ$p_r\#$.

Таким образом, для определения значения функции Якобсталя для ПСВ$p_r\#$ достаточно просмотреть только интервалы между вычетами ПСВ$p_r\#$, полученные после удаления вычетов $p^2_r,p_rp_{r+1},...$ и сравнить максимальное значение интервала с запомненным ранее значением для ПСВ$p_{r-1}\#$. Максимальное значение из этих двух снова запоминается и далее процедура повторяется для следующего ПСВ и.т.д.

Учитывая симметричность ПСВ$p_r\#$, достаточно просмотреть только интервалы между вычетами на отрезке $[1,p_r\#/2]$.

[Dmitriy40]

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

Таким образом, для определения значения функции Якобсталя для ПСВ$p_r\#$ достаточно просмотреть только интервалы между вычетами ПСВ$p_r\#$, полученные после удаления вычетов $p^2_r,p_rp_{r+1},...$ и сравнить максимальное значение интервала с запомненным ранее значением для ПСВ$p_{r-1}\#$. Максимальное значение из этих двух снова запоминается и далее процедура повторяется для следующего ПСВ и.т.д.

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

[vicvolf]

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

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

Таким образом, для определения значения функции Якобсталя для ПСВ$p_r\#$ достаточно просмотреть только интервалы между вычетами ПСВ$p_r\#$, полученные после удаления вычетов $p^2_r,p_rp_{r+1},...$ и сравнить максимальное значение интервала с запомненным ранее значением для ПСВ$p_{r-1}\#$. Максимальное значение из этих двух снова запоминается и далее процедура повторяется для следующего ПСВ и.т.д.

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

Вы наверно не поняли. Я нигде не писал, что максимальный интервал образуется, как сумма максимальных. Какие интервалы получатся после удаления этих вычетов - такие получатся. Других новых интервалов нет. Я просто писал, что максимальный интервал определяется, как максимум из двух интервалов. Один из которых является максимальным на предыдущем шаге, а другой максимальным на этом.

[Dmitriy40]

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

Один из которых является максимальным на предыдущем шаге,

Нет! Не обязательно является!
Именно этот алгоритм я и назвал "жадным" и именно он и реализован в моей программе. Как видели он вовсе не даёт правильные максимальные интервалы.

-- 12.11.2021, 13:24 --

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

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

[vicvolf]

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

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

Это опять не о том. Максимум интервала на $n$ -ом шаге является максимумом за шаги от 1 до $n$, а максимум на $n+1$- шаге является максимумом за шаги $n$ и $n+1$, т.е. за шаги от 1 до $n+1$. И не надо клеить ярлыки, так как все могут ошибаться.

[Dmitriy40]

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

а максимум на $n+1$- шаге является максимумом за шаги $n$

Поясните ещё подробнее. Например про $73\#$ с $d=190$.
Потому что я в очередной раз говорю что это не так и даже пример привёл где это не так. Не является. Во всяком случае не всегда.

Что размеры интервалов монотонны понятно, но вот каждый следующий интервал вовсе не обязательно включает в себя именно максимальный интервал на предыдущем шаге. Повторю, я же именно так и написал программу в соседней теме, которая в результате сильно занижает максимальные интервалы. Т.е. этот алгоритм уже был давно проверен и отвергнут в этом плане (что не выдаёт точные максимальные интервалы), а Вы снова пытаетесь это утверждать.

[Yury_rsn]

Dmitriy40
Подскажите, пожалуйста, а можно ли как-то попытаться сделать частичный перебор каким-то другим образом, а не в таблицах?

Перебор в таблицах я описывал недавно:

Цитата:

Таблица цепочек для какого-то конкретного праймориала позволяет делать перебор в несколько приемов.
Посмотрите, пожалуйста, таблицу для 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

Вот эту логику как-то можно иначе реализовать,
или только скрипты писать в электронных таблицах?

Первый следующий кандидат на разветвление - 47#, d=100

[Dmitriy40]

Yury_rsn
Решение любой (исключения в данной теме неактуальны) чётко сформулированной задачи можно записать в виде алгоритма (т.е. фактически программы). Разумеется и эти манипуляции с таблицами можно переформулировать на языке алгоритма, который реализовать хоть скриптами в таблицах, хоть на другом языке программирования.
Вопрос лишь понять что именно Вы там делаете с таблицами ... Какие-то переборы в ячейках, удаление чисел в ячейках, что-то там появляется и исчезает ... Я даже не пытался разбираться. Мне понятнее математическая запись, через остатки по модулям, вычеты, делимость. Здесь же реально надо сначала понять что и почему происходит в таблице, потом сформулировать это всё математически, и лишь потом думать как это реализовать в программе. И все три этапа затратны.

-- 13.11.2021, 13:29 --

Вот Вы говорите что после 37# следующий кандидат на непонятное разветвление (видимо это случаи когда максимальных интервалов больше двух?) лишь 47#, т.е. 41# и 43# вычисляются без множества вариантов, единственным образом? Так приведите как именно. Потому что в той статье было указано что для 43# максимальных интервалов 48 варианта, не 2.

[Yury_rsn]

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

Вот Вы говорите что после 37# следующий кандидат на непонятное разветвление (видимо это случаи когда максимальных интервалов больше двух?) лишь 47#, т.е. 41# и 43# вычисляются без множества вариантов, единственным образом? Так приведите как именно. Потому что в той статье было указано что для 43# максимальных интервалов 48 варианта, не 2.

С удовольствием объясню. Только опять надо обязательно вспомнить, что это не моя идея, а vorvalm.

Прошу рассмотреть таблицу со случаем 43# - https://docs.google.com/spreadsheets/d/ ... sp=sharing
Название - "n=14_43#_d=90"

Я в ней сейчас открыл доступ для редактирования онлайн. Можно экспериментировать прямо сразу там, если что.

Теперь.
Рассмотрим прямоугольник H4:AJ15 - я его обвел синей рамкой. Это и есть таблица минимальных делителей каждого числа из соответствующего интервала Якобсталя.

В данном случае, мы берем значение из таблицы Гербича для n=14.
Это будет 253772227953735327711085906760492231684 - первое число интервала длиной 90.

Но удобнее взять "нулевое" число, нечетное. Т.е., отнять единицу. И к этому получившемуся начальному числу уже прибавлять попеременно 2 и 4, чтобы рассматривать нечетные числа, не кратные 3.
В столбце H мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+2"
Это число 7.

В столбце I мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+6"
Это число 13.

В столбце J мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+8"
Это число 5.
И так далее.

Как видим, в некоторых строках этой таблицы появляется по два и больше чисел.
Это строки - 5, 7, 11, 13, 17, 19, 23, 31.
А в других строках только по одному числу.
Строки - 29, 37, 41, 43.
(В ячейках A4:A15, которые взяты в зеленую рамочку, посчитано количество чисел построчно)

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

А в тех строках, где находится по одному числу, - намного проще.
Ниже основной таблицы приведены варианты таблиц со взаимно перемещенными между собой одиночными числами.
Каждое такое смещение соответствует _новому_ интервалу. Новый интервал теперь будет строиться не от числа 253772227953735327711085906760492231684-1, а от какого-то другого числа А.
Но все соответствующие делимости сохраняются.
Так А+2 - делится на 7
"А+6"- делится на 13.
"А+8"- делится на 5. И так далее.
Но!
"А+42"- делится не на 29, а на 37.
а "А+50"- делится не на 37, а на 29.

Таких перестановок из четырех чисел может быть 4!=24.
Все интервалы несимметричны, поэтому не совпадают с зеркальными отражениями.
Следовательно, всего интервалов Якобсталя, исходя из количества одиночных чисел в строках таблицы, должно быть 24 умножить на два, т.е., 48 шт.

[Dmitriy40]

Сама идея понятна, два замечания.

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

В столбце H мы указываем наименьшие делители числа "253772227953735327711085906760492231684+2"
Это число 7.

Нет, это число 2.

Далее, в ячейке H5 записано условие делимости разности двух чисел, первое из которых это смещение в интервале, с ним всё понятно, а второе берётся из ячейки G5 - и это как раз то число, которое и надо перебирать при поиске максимального интервала. Что моя программа (в соседней теме) собственно и делает.
Поэтому вопрос: а откуда Вы собственно взяли числа в столбце G? Точнее по какому правилу их взяли вот такими? Мне пока непонятно.
Я вот ради интереса заменил число в G4 с 8 на 0 и тут же получил 6 дырок в строке 3. Так почему у Вас там 8 стоит?
На самом деле весь вопрос поиска интервалов сводится к поиску чисел в столбце G, таких чтобы не оставалось дырок в синем прямоугольнике. Но как это делать без полного перебора всех вариантов непонятно.

-- 13.11.2021, 23:09 --

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

-- 13.11.2021, 23:18 --

Если интересно, то я в программе поступаю следующим образом: в порядке от верхней строки (там где простое число 3, у Вас его нет) перебираю все варианты смещений (столбец G) и считаю сколько остаётся дырок в интервале, из найденных вариантов выбираю тот где дырок остаётся меньше (или чтобы заполнилась самая левая дырка) и перехожу к следующему простому (вниз по таблице). В итоге проверяю сколько левых столбцов заполнились - это и будет размер найденного интервала (а его положение в примориале можно получить из смещений в столбце G по китайской теореме об остатках). Это основная идея, реально там ещё пара-тройка оптимизаций накручена, но не принципиальных. Результат - интервал не максимально возможный, зато можно посчитать хоть стотысячные примориалы.

-- 14.11.2021, 00:00 --

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

[Yury_rsn]

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

Нет, это число 2.

Я эту ошибку почти сразу исправил, но вы успели раньше

-- 14.11.2021, 02:38 --

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

Поэтому вопрос: а откуда Вы собственно взяли числа в столбце G? Точнее по какому правилу их взяли вот такими? Мне пока непонятно.

Все формулы, и в столбце G, и во внутри синего прямоугольника - зависят от параметра в столбце D.
Оранжевые числа в этом столбце (в оранжевой рамке). И еще есть оранжевые числа в первой строке - номера столбцов. Т.е., число в столбце D - это номер столбца, где встречается этот множитель.
Ставишь номер любого числа, и тут же по нему рассчитывается вся остальная цепочка.

Они найдены с помощью факторизации соответствующих сумм - "число Гербича, минус один, плюс число из второй строки".
Сервис https://ru.numberempire.com/numberfactorizer.php - разложение на простые множители чисел, длиной до 70 символов.

-- 14.11.2021, 02:50 --

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

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

Всё-таки, я говорю чуть-чуть о другой задаче.
Не надо искать максимальный интервал для данного праймориала. Он предполагается известным (функция Якобсталя).
И более того, мы его "вживую построили" - исходя из расчетов Гербича.

А вопрос звучит так:
Если предположить, что для некоторых праймориалов интервалы "разветвляются", то можно ли попытаться построить эти другие раскладки в данном праймориале?
Или с помощью опять простого перебора, или как-то по-другому.

-- 14.11.2021, 02:56 --

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

я в программе поступаю следующим образом: в порядке от верхней строки (там где простое число 3, у Вас его нет) перебираю все варианты смещений (столбец G) и считаю сколько остаётся дырок в интервале,

А попробуйте поработать с оранжевыми числами, а не с разностями из G, пожалуйста.
Интересно, насколько у вас поменяется впечатление об общей логике процесса.

[Dmitriy40]

Лучше не стало:

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

В столбце H мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+2"
Это число 7.

Это число 3.

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

В столбце I мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+6"
Это число 13.

Это число 29.

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

В столбце J мы указываем наименьшие делители числа "253772227953735327711085906760492231684-1+8"
Это число 5.

Это число 3.

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

Все формулы, и в столбце G, и во внутри синего прямоугольника - зависят от параметра в столбце D.
...
Они найдены с помощью факторизации соответствующих сумм - "число Гербича, минус один, плюс число из второй строки".

Поясните ещё раз, как именно найдены числа в столбце D. На любом конкретном примере. Да, вижу что G получается из них, просто пересчёт номера в смещение.
Разложение на простые множители известная процедура и PARI/GP с ней справляется великолепно. Хотя кому-то удобнее на сайте.

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

А попробуйте поработать с оранжевыми числами, а не с разностями из G, пожалуйста.
Интересно, насколько у вас поменяется впечатление об общей логике процесса.

Ни насколько не поменяется - это однозначно связанные числа.
Повторю, может я плохо выразился, но это всё вполне очевидно. Не очевиден лишь один момент - как обходитесь без полного перебора чисел в столбце D (из которого тривиально получается G).
Для меня единственное достоинство этой таблицы - всё происходит наглядно, можно руками подбирать что хочешь. Но решать задачу это никак не облегчает, ведь вся математика и методы уже известны и так.

-- 14.11.2021, 02:13 --

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

А вопрос звучит так:
Если предположить, что для некоторых праймориалов интервалы "разветвляются", то можно ли попытаться построить эти другие раскладки в данном праймориале?
Или с помощью опять простого перебора, или как-то по-другому.

И снова я не понимаю задачу: что значит "разветвляется"? Более одного (двух зеркальных) варианта допустимо? Так это легко понять по количеству простых которые присутствуют в прямоугольнике ровно один раз и наличию зеркальной симметрии (может быть и не одной). Можно даже аккуратно подсчитать без перебора.
И кстати без пропущенных троек симметрию увидеть сильно сложнее.

-- 14.11.2021, 02:21 --

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

Поясните ещё раз, как именно найдены числа в столбце D. На любом конкретном примере.

Вопрос снимаю. Раз уж Вы имеете число 253772227953735327711085906760492231684, то из него получается всё что надо.

-- 14.11.2021, 02:38 --

Э, а откуда вообще взялось число 253772227953735327711085906760492231684? Ведь оно относится к 101# с d=264, а у Вас в таблица лишь до 43# с d=90.
Вот наименьший простой делитель всех нечётных чисел начиная с 253772227953735327711085906760492231683:
181, 3, 41, 29, 3, 7, 5, 3, 61, 13, 3, 5, 7, 3, 23, 89, 3, 11, 47, 3, 73, 5, 3, 19, 83, 3, 5, 17, 3, 79, 31, 3, 29, 7, 3, 13, 5, 3, 97, 11, 3, 5, 19, 3, 17, 53, 3, 7, 13, 3, 11, 5, 3, 67, 7, 3, 5, 71, 3, 43, 23, 3, 101, 59, 3, 47, 5, 3, 7, 61, 3, 5, 11, 3, 13, 7, 3, 37, 17, 3, 19, 5, 3, 11, 41, 3, 5, 13, 3, 7, 29, 3, 31, 73, 3, 17, 5, 3, 53, 19, 3, 5, 43, 3, 89, 11, 3, 83, 79, 3, 7, 5, 3, 13, 37, 3, 5, 7, 3, 29, 67, 3, 59, 31, 3, 41, 5, 3, 71, 17, 3, 5, 883
Видно что для 43# d будет всего лишь 16, оборвётся на числе 61.

-- 14.11.2021, 03:05 --

vicvolf
Кстати это свеженький пример против Вашего алгоритма/утверждения: как хорошо видно для 101# максимальный интервал в 264 набран объединением двух интервалов 124+140, ни один из которых не является максимальным для 97#.

[vicvolf]

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

Что размеры интервалов монотонны понятно,

Да, действительно функция Якобсталя строго возрастает с ростом $p_n$:

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

n _ pn _ h(n) _ n_seq

2 _ 3 _ 4 _ 1
3 _ 5 _ 6 _ 2
4 _ 7 _ 10 _ 2
5 _ 11 _ 14 _ 2
6 _ 13 _ 22 _ 2
7 _ 17 _ 26 _ 2
8 _ 19 _ 34 _ 2
9 _ 23 _ 40 _ 12
10 _ 29 _ 46 _ 2
11 _ 31 _ 58 _ 2
12 _ 37 _ 66 _ 24
13 _ 41 _ 74 _ 2
14 _ 43 _ 90 _ 48
15 _ 47 _ 100 _ 24
16 _ 53 _ 106 _ 240
17 _ 59 _ 118 _ 60
18 _ 61 _ 132 _ 12
19 _ 67 _ 152 _ 144
20 _ 71 _ 174 _ 52
21 _ 73 _ 190 _ 24
22 _ 79 _ 200 _ 144
23 _ 83 _ 216 _ 16
24 _ 89 _ 234 _ 16
25 _ 97 _ 258 _ 4
26 _ 101 _ 264 _ 40
27 _ 103 _ 282 _ 4
28 _ 107 _ 300 _ 24
29 _ 109 _ 312 _ 204
30 _ 113 _ 330 _ 48
31 _ 127 _ 354 _ 2
32 _ 131 _ 378 _ 2
33 _ 137 _ 388 _ 8
34 _ 139 _ 414 _ 22
35 _ 149 _ 432 _ 4
36 _ 151 _ 450 _ 18
37 _ 157 _ 476 _ 4
38 _ 163 _ 492 _ 28
39 _ 167 _ 510 _ 4
40 _ 173 _ 538 _ 4

Поэтому надо проверить только интервалы, которые получаются после удаления вычетов, делящихся на $p_n$. Любая ПСВ_$p_n$# начинается с 1, потом следует $p_{n+1}$. Так что вычеты, делящиеся на $p_n$ начинаются с $p_^2_n$, затем $p_np_{n+1}$, затем $p_np_{n+2}$ и.т.д.

Минимальное расстояние между этими вычетами $2p_n$, поэтому если интервал больше $2p_n$, то могут объединяться и три интервала при определенных условиях. Сейчас разговор не об этом, а о том, что не надо каждый раз проверять все интервалы, а только которые получаются после удаления этих вычетов.

[Yury_rsn]

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

Э, а откуда вообще взялось число 253772227953735327711085906760492231684? Ведь оно относится к 101# с d=264, а у Вас в таблица лишь до 43# с d=90

Блин, айм сорри, как говорится. Просто на автомате не туда поглядел, взял не то число.
Из таблицы http://oeis.org/A048670/a048670.txt - 14 90 18729282685998828

Естественно, для 43# с d=90 все расчеты идут от числа 18729282685998828

-- 14.11.2021, 14:25 --

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

И снова я не понимаю задачу: что значит "разветвляется"? Более одного (двух зеркальных) варианта допустимо?

Разветвление - это хорошо видно на примере из 37#.
post1517825.html#p1517825
- есть два варианта расположения чисел, которые не сводимы друг к другу простыми перестановками.
Все цепочки по-разному расположены по отношению к неподвижным пятеркам.

В первом варианте - три одиночных числа, и во втором - три одиночных числа.
Если бы не было этого разветвления на два варианта, а существовал бы только один, то всего бы количество n_seq составляло бы 12. А из-за "разветвления" - общее количество интервалов, длиной 66 на ПСВ праймориала 37#, составляет 24 шт.

Т.е., в общем случае, при рассмотрении в таблице Зиллера (Циллера ?) иногда видим совпадение с нашими данными, а иногда видим, что у Зиллера чисел больше, чем получается из наших расчетов по свободным единицам

-- 14.11.2021, 14:28 --

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

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

Да, удобная визуализация.

Но именно эта новая наглядность позволяет предположить, что в рассматриваемом паззле чего-то не хватает.

[Dmitriy40]

vicvolf
Всё равно не понимаю в чём профит.
Вот рассмотрим $37\#$ с $d=66$, первый раз интервал встречается на $8720486098463$, при этом кратное $37$ число будет на смещении $+38$ от начала интервала (смещение $+1$ проигнорируем как чётное), при этом оно раскладывается в множители $37\cdot4409\cdot53456297=8720486098501$. Видно что число состоит из произведения трёх простых каждое в первой степени. Следующее большее число с минимальным простым делителем $37$ будет по смещению $+408$ и оно раскладывается уже в произведение четырёх простых. Следующее аналогичное по смещению $+630$ раскладывается на два простых. Т.е. варианты самые разные, не только произведение $37$ на другое простое.

Ещё момент. В интервале $-6600\ldots+6600$ от $8720486098463$ (100 максимальных интервалов влево и 100 вправо) чисел с минимальным простым делителем $37$ насчитывается $57$ штук, все их надо проверять так как именно там может образоваться максимальный интервал. Выходит что проверить надо $57/200=29\%$ интервалов. Вы простите, но ускорение втрое это вообще ни о чём.
Может быть число слишком мало? Проверим на $251\#$ с $d=858$, возьмём не мелочась по 1000 интервалов влево и вправо, там будет $689$ чисел с минимальным простым делителем $251$, т.е. эффективность составила $689/2000=34\%$, даже хуже чем для небольших чисел.
Да, само по себе ускорение втрое конечно неплохо, ужасно лишь что оно не растёт с ростом $p$, а вот объём перебора растёт, и очень быстро.

-- 14.11.2021, 14:00 --

Yury_rsn
Да, сегодня до меня наконец дошло что Вы имеете в виду.
Факт что есть некие "разветвления" установить просто: количество интервалов не равно $2\cdot n!$, где $n$ это количество простых, входящих в интервал единожды.
При поиске всех вариантов такие простые можно не рассматривать, работать только с остальными.
Но вот как найти все варианты остальных без перебора я не знаю, там не всегда есть симметрия — потому что бывают например 5 вариантов, для 59# и 197# и 199#, или 11 вариантов для 139#, а по симметриям должно быть всегда чётное число. Т.е. выше про возможность подсчёта по симметриям был неправ.