Regex for divisibility by 123 in binary strings

Is there a regex that checks for divisibility by 123 in binary strings?

This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative Exercises section).

Creating a regex to check if a binary string is divisible by 3 is simple: (0|1(01*0)*1) *

A regex to check if a binary string is divisible by 2 is also simple: (0|1)*0

And there are many questions on the Internet asking for a regex for divisibility by 7.

However, I could not find any resources related to a regex for checking if a binary string is divisible by 123.

These are the representations of some multiples of 123 in binary:

0 = 0

123 = 1111011

246 = 11110110

369 = 101110001

492 = 111101100

615 = 1001100111

738 = 1011100010

861 = 1101011101

984 = 1111011000

1107 = 10001010011

1230 = 10011001110

There doesn’t seem to be a pattern that stands out (even though there is probably one, since the question to check 123-divisibility with a regex exists).

There are, however, some similarities in some strings:

123, 246, 492 and 984 in binary are basically the same, but 246 has an extra 0 in the end, 492 has two extra 0s in the end and 984 has three extra 0s in the end.

369 and 738 in binary are basically the same, but 738 has an extra 0 in the end.

615 and 1230 in binary are basically the same, but 1230 has an extra 0 in the end.

Any ideas for a regular expression for such strings? Thanks!

• This question and my answer prompted me to ask another question cs.stackexchange.com/questions/89814/…, which might also be relevant to people interested in the present question.
– kne
Apr 12, 2018 at 15:47

Here is a way that succeeds, albeit with a lot of work.

First, construct a DFA for the language. That is actually quite simple: It has states $0$ through $122$ (for the remainders), start state and only accepting state is $0$, the transitions from state $n$ go to $(2n \mod 123)$ for label $0$ and to $(2n+1 \mod 123)$ for label $1$.

Now, convert that DFA to a regular expression. The result is not likely to be simple, small or nice.

If you use an extension to regular expressions that allows intersection, you can also do the above with $41$ instead of $123$ and then intersect with the expression you have for divisibility by $3$.

• "The result is not likely to be simple...." That's an understatement. Mar 21, 2018 at 19:15
• This looks like a great idea, but I wonder if there is a simpler approach, that does not require constructing the DFA and converting it to the RE. For example, the regular expression 0|11110110* describes 5 out of the 11 numbers that I mentioned on the question. Maybe there are other patterns that can be used to describe binary strings divisible by 123 in general. Mar 22, 2018 at 14:44
• Also, the DFA-to-regular-expression converters that I have found seem to work for up to 14 states, increasing time exponentially for every state added in the DFA. Is there a way to do this conversion in a DFA with 123 states in a efficient way? Mar 23, 2018 at 4:05
• @Rene Argento: I believe that it cannot be done efficiently. I don't have hard data; the best I could find is en.wikipedia.org/wiki/… mentioning without citation that divisibility by 11 in base 10 does not have a small regex. (And implying with citation that DFA to regex conversion is exponential or worse.)
– kne
Mar 23, 2018 at 17:06
• I believe the same. I waited a few more days to see if anyone else had any other ideas, but it seems that this is the only approach. Apr 10, 2018 at 20:51