Can I use regular expressions to search for multiples of a number?

Question

I'm trying to search a big project for all examples of where I've declared an array with [48] as the size or any multiples of 48.

Can I use a regular expression function to find matches of 48 * n?

Thanks.

Answer 1

Here you go (In PHP's PCRE syntax):

^(0*|(1(01*?0)*?1|0)+?0{4})$

Usage:

preg_match('/^(0*|(1(01*?0)*?1|0)+?0{4})$/', decbin($number));

Now, why it works:

Well we know that 48 is really just 3 * 16. And 16 is just 2*2*2*2. So, any number divisible by 2^4 will have the 4 most bits in its binary representation 0. So by ending the regexp with 0{4}$ is equivalent to saying that the number is divisible by 2^4 (or 16). So then, the bits to the left need to be divisible by 3. So using the regexp from this answer, we can tell if they are divisible by 3. So if the whole regexp matches, the number is divisible by both 3 and 16, and hence 48...

QED...

(Note, the leading 0| case handles the failed match when $number is 0). I've tested this on all numbers from 0 to 48^5, and it correctly matches each time...

Answer 2

A generalization of your question is asking whether x is a string representing a multiple of n in base b. This is the same thing as asking whether the remainder of x divided by n is 0. You can easily create a DFA to compute this.

Create a DFA with n states, numbered from 0 to n - 1. State 0 is both the initial state and the sole accepting state. Each state will have b outgoing transitions, one for each symbol in the alphabet (since base-b gives you b digits to work with).

Each state represents the remainder of the portion of x we've seen so far, divided by n. This is why we have n of them (dividing a number by n yields a remainder in the range 0 to n - 1), and also why state 0 is the accepting state.

Since the digits of x are processed from left to right, if we have a number y from the first few digits of x and read the digit d, we get the new value of y from yb + d. But more importantly, the remainder r changes to (rb + d) mod n. So we now know how to connect the transition arcs and complete the DFA.

You can do this for any n and b. Here, for example, is one that accepts multiples of 18 in base-10 (states on the rows, inputs on the columns):

   |  0  1  2  3  4  5  6  7  8  9
---+-------------------------------
→0 |  0  1  2  3  4  5  6  7  8  9  ←accept
 1 | 10 11 12 13 14 15 16 17  0  1
 2 |  2  3  4  5  6  7  8  9 10 11
 3 | 12 13 14 15 16 17  0  1  2  3
 4 |  4  5  6  7  8  9 10 11 12 13
 5 | 14 15 16 17  0  1  2  3  4  5
 6 |  6  7  8  9 10 11 12 13 14 15
 7 | 16 17  0  1  2  3  4  5  6  7
 8 |  8  9 10 11 12 13 14 15 16 17
 9 |  0  1  2  3  4  5  6  7  8  9
10 | 10 11 12 13 14 15 16 17  0  1
11 |  2  3  4  5  6  7  8  9 10 11
12 | 12 13 14 15 16 17  0  1  2  3
13 |  4  5  6  7  8  9 10 11 12 13
14 | 14 15 16 17  0  1  2  3  4  5
15 |  6  7  8  9 10 11 12 13 14 15
16 | 16 17  0  1  2  3  4  5  6  7
17 |  8  9 10 11 12 13 14 15 16 17

These get really tedious as n and b get larger, but you can obviously write a program to generate them for you no problem.