Регулярные выражения делимости чисел

Меня с детства привлекала тема признаков делимости числа. Особенно удивительно было узнать про признаки делимости на 3 и на 9, когда путем простого сложения всех чисел и проверки результата можно было узнать делится ли изначальное число на эту цифру. Кроме того было интересно узнать, что существует регулярное выражение определяющее простоту числа. Но основной фокус там в том, что число записывается в унарном виде.

И вот пару лет назад я встретил еще одну интересную задачу по написанию регулярного выражения для определения делится ли искомое число на 7. Само число при этом написано в двоичном виде. Признаки делимости на 7 существуют и для двоичной и для десятичной записи, но как правило они требуют производить операции умножения, сложения и рекурсивно проверять делимость уже получившегося в итоге этих действий меньшего числа, что не очень подходит для написания регулярного выражения. Я предполагал, что каким то образом могут помочь сложные операторы: условное сопоставление (позиционные проверки), обратные ссылки итд, но не разобрался как их использовать конкретно для данной задачи. Гораздо больше я думал в сторону более простой регулярки с использованием только оператора ИЛИ, квантификаторов и скобок. Остановился на построении графа остатков от деления следуя, по которому можно получить остаток заданного числа, но уперся в то, что всякое выражение с использованием скобок, но без ссылок — это в итоге дерево и поэтому произвольный граф туда не ложится. Это как пытаться хранить произвольный граф в JSON или XML — можно, но нужно будет вводить идентификаторы узлов и поля ссылок, а в то же время хранение простого дерева этого не потребует.

Недавно появилась в открытом доступе рассуждающая модель DeepSeek R1 и я попытался спросить у нее. Но к сожалению (или к счастью) она после 462 секунд рассуждений и выдав примерно 26 KB текста все же не смогла найти правильный ответ. Но в этом рассуждении я нашел интересные мысли, которые в каком то виде у меня уже были, но видимо недостаточно четко кристаллизовались. Но после прочтения этого потока мыслей начала складываться более четкая картина.

Как ИИ заметил регулярное выражение может быть построено по некоторому автомату состояний, содержащему некоторый контекст. Контекстом нашей регулярки должен быть текущий остаток от деления уже просмотренной части числа. Новый остаток от деления зависит только от текущего анализируемого знака двоичного числа и текущего остатка от деления лежащего в контексте. В целом это немного напоминает свойство цепей Маркова из теории вероятности — если мы знаем значение, полученное каким-то процессом в заданный момент времени, то не получим никакой дополнительной информации о будущем поведении процесса, собирая другие сведения о его прошлом. У нас таким значением служит остаток от деления предыдущей части числа. Для каждого состояния S и бита b новое состояние вычисляется как (2 * S + b) % 5. Так же модель правильно навела на мысль, что начальным контекстом должен быть остаток 0 и конечным контекстом тоже 0. Другими словами надо найти регулярно выражение находящее все пути, переводящие из контекст 0 в контекст 0. Обозначим его как R0. Так как таких частей может быть много в заданном числе, то оборачиваем его квантификатором соответствия одному или более раз.

Итоговое выражение = (R0)+

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

Для примера рассмотрим граф остатков деления на 5. Так как таких чисел может быть всего 5, то получим 5 нод. Обозначим состояния остатков S0..S4

Ту же самую диаграмму можно представить в виде системы уравнений, обозначив через R0..RN регулярные выражения сопоставляющиеся со всеми путями из контекста N в нулевой контекст:

R0 = 0(R0) | 1(R1) R1 = 0(R2) | 1(R3) R2 = 1(R0) | 0(R4) R3 = 1(R2) | 0(R1) R4 = 1(R4) | 0(R3)

Здесь могут быть небольшие отличия от синтаксиса собственно регулярных выражений:

• добавились ссылки между выражениями

• добавились знаки равенства

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

• но в целом оставшиеся знаки — скобки, знак ИЛИ, конкретные символы цифр — соответствуют синтаксису регулярных выражений.

Так же надо не забывать, что при выходе из всех этих выражений мы должны попадать в контекст с остатком 0. Если об этом начать забывать, то будут получаться ошибки в результатах преобразований рассмотренных ниже.

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

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

R0 = 0 | 1(R1)

С первым все просто — ветвь 0 получает контекст 0 и возвращает его же. А так как все указанные парсеры возвращают в контекст 0 по умолчанию, то явная ссылка на R0 здесь излишняя. А при получении 1 мы попадаем в контекст S1 и чтобы выйти из него в контекст 0 нам все таки нужен парсер R1.

R4 = 1*0(R3)

Последнее выражение чуть сложнее, так как у него только один выход — через контекст S3 в который можно попасть только со значением 0. Но при этом можно от 0 шагов до бесконечности оставаться в контексте S4 получая поток единиц, поэтому добавляем единице квантификатор *. Между двумя этими альтернативами здесь поставим оператор И, так как ветвь 0 обязательно должна быть для единственно возможного выхода из контекста S4 и итогового достижения контекста S0, а ветвь 1 и так опциональна из за квантификатора *. Хотя эти ветки по итогу все равно работают по ИЛИ, но все же мы вынуждены применить И вместо ИЛИ, так как ветвь с цифрой 1 возвращает контекст S4 чтобы выйти из которого нам нужен парсер R4, а мы хотим избавится от ссылки R4 на саму себя.

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

R2 = 1 | 0(R4)

В итоге получим чуть упрощенную систему выражений с меньшим количеством ссылок:

R0 = 0     | 1(R1) R1 = 0(R2) | 1(R3) R2 = 1     | 0(R4) R3 = 1(R2) | 0(R1) R4 = 1*      0(R3)

Теперь у нас в выражениях отсутствуют рекурсивные ссылки и мы можем заняться их подстановкой друг в друга, чтобы в итоге из графа получить дерево парсеров. Мы уже можем отложить в сторону парсер RO, так как ему кроме применения R1 больше ничего не нужно знать. Теперь можем избавиться и от R4 подставив его в единственное место откуда он может использоваться — контекст с состоянием S2 с парсером R2:

R2 = 1 | 01*0(R3)

В итоге получим систему из всего 3 зависимых парсеров:

R1 = 0(R2) | 1(R3) R2 = 1     | 01*0(R3) R3 = 1(R2) | 0(R1)

Теперь можем заняться подстановкой R2 в R3 чтобы избавится от зависимости R3 от R2:

R3 = 1(1 | 01*0(R3)) | 0(R1)

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

R3 = 11 | 101*0(R3) | 0(R1)

Теперь проделывая тот же трюк что и ранее заменяем ИЛИ на И, вводим квантификатор * и убираем таким образом циклическую ссылку:

R3 = (101*0)*(11 | 0(R1))

Теперь подставим R3 в R1 и таким же способом раскрываем скобки и убираем циклическую ссылку R1 на саму себя:

R1 = 0(R2) | 1((101*0)*(11 | 0(R1))) R1 = 0(R2) | 1(101*0)*11   | 1(101*0)*0(R1) R1 = (1(101*0)*0)* ( 0(R2) | 1(101*0)*11 )

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

R1 = (1(101*0)*0)*(0(R2) | 1(101*0)*11) R2 =  1 | 01*0(R3) R3 = (101*0)*(11 | 0(R1))

С зависимостями в форме кольца, одним входом на парсере R1 и одним возможным выходом на парсере R2:

Хотя все парсеры по условию в конце должны возвращать состояние 0, но пока только парсер R2 содержит явное условие выхода — ветвь 1, остальные парсеры лишь ссылаются на другие парсеры для условия выхода.

Затем подставим R2 в R1:

R1 = (1(101*0)*0)*(0(1 | 01*0(R3)) | 1(101*0)*11)

И наконец R3 в R1

R1 = (1(101*0)*0)*(0(1 | 01*0((101*0)*(11 | 0(R1)))) | 1(101*0)*11)

Осталось самое муторное — избавится от рекурсии R1 на саму себя. Для этого применим все тот же дистрибутивный закон, но заменив части выражения на обозначения и символ | на + для более привычного вида:

a = (1(101*0)*0)* b = 0 c = 1 d = 01*0 e = (101*0)* f = 11 g = 0(R1) h = 1(101*0)*11  R1 = a * ( b * ( c + d * ( e * ( f + g ) ) ) + h ) R1 = a * ( b * ( c + d * ( ef + eg ) ) + h ) R1 = a * ( b * ( c + def + deg ) + h ) R1 = a * ( bc + bdef + bdeg + h ) R1 = abc + abdef + abdeg + ah  R1 = (1(101*0)*0)*01 | (1(101*0)*0)*001*0(101*0)*11 | (1(101*0)*0)*001*0(101*0)*0(R1) | (1(101*0)*0)*1(101*0)*11

Теперь применим тот же трюк заменив циклическую ссылку на квантификатор и оператор ИЛИ на И

R1 = ((1(101*0)*0)*001*0(101*0)*0)*   ( (1(101*0)*0)*01 | (1(101*0)*0)*001*0(101*0)*11 | (1(101*0)*0)*1(101*0)*11 )

В итоге подставим получившийся парсер в R0 и получим:

R0 = (0|1(((1(101*0)*0)*001*0(101*0)*0)*((1(101*0)*0)*01|(1(101*0)*0)*001*0(101*0)*11|(1(101*0)*0)*1(101*0)*11)))+

Теперь он не содержит каких либо ссылок, и мы обошлись без каких либо сложных конструкций регулярных выражений, оставив только квантификаторы, скобки, операции И и ИЛИ. Осталось только проверить насколько оно вообще получилось рабочим. Для этого напишем небольшой PowerShell код вставляющий в буфер обмена последовательность цифр от 1 до 5000 в десятичном и двоичном форматах:

Set-Clipboard (1..5000 | %{ $_.ToString() + " = " + [System.Convert]::ToString($_,2) })

Теперь можем вставить это выражение в онлайн инструмент https://regex101.com/

Получаем что в 5000 цифр получили 1000 совпадений, что примерно похоже на правду. На всякий случай сделал более сложный пример из 2000 битов, выданный генератором случайных чисел

Для сравнения вот как отработало регулярное выражение предложенное моделью DeepSeek R1

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

Кому интересно решение от исходной задачи с делителем 7, то вот оно ниже, только почему то оно не проходит по тестам в codewars, возможно кто то из нас где то ошибся:

(0|1((101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*0(0|1(00(1*0))*1)(1(0|1(00(1*0))*1))*0)*((101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*0(0|1(00(1*0))*1)(1(0|1(00(1*0))*1))*11(00(1*0))*01|(101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*01(00(1*0))*01|(101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*101*0(00(1*0))*01|(101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*101*0(00(1*0))*1(1(0|1(00(1*0))*1))*11(00(1*0))*01|(101*0(00(1*0))*1(1(0|1(00(1*0))*1))*0)*11))+