Given a decimal number N as a string of digits, how do I check if it's divisible by M using regular expressions only, without converting to int?

M=2, 4, 5, 10 are obvious. For M=3 some interesting insights here: Regex filter numbers divisible by 3

Can anyone provide a solution for M=7, 9, 11, 13 etc? A generic one?

Testing code (in python, but feel free to use any language):

M = your number, e.g. 2
R = your regexp, e.g., '^[0-9]*[02468]$'

import re
for i in range(1, 2000):
    m = re.match(R, str(i))
    if i % M:
        assert not m, '%d should not match' % i
    else:
        assert m, '%d must match' % i

For those curious, here's an example for M=3 (assumes an engine with recursion support):

^
(
    | [0369]+ (?1)
    | [147] (?1) [258] (?1)
    | [258] (?1) [147] (?1)
    | ( [258] (?1) ) {3}
    | ( [147] (?1) ) {3}
)
$

Upd: for more discussion and examples see this thread. The expression posted there turned out to be buggy (fails on 70*N), but "how to get there" part is very educative.

regex math
Edit
Report