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.

Answer 3

1|48|2304|110592|5308416

You are unlikely to have declared an array of size 48^5 or larger.

Answer 4

No, regular expressions can't calculate multiples (except in the unary number system: decimal 4 = unary 1111; decimal 8 = unary 11111111, so the regex ^(1111)+$ matches multiples of 4).

Answer 5

import re

# For real example,
# construction of a chain with integers multiples of 48 
# and integers not multiple of 48.
from random import *
w   =   [ 48*randint( 1,10) for j in xrange(10) ]
w.extend( 48*randint(11,20) for j in xrange(10) )
w.extend( 48*randint(21,70) for j in xrange(10) )
a = [ el if el%48!=0 else el+1 for el in sample(xrange(1000),40) ]
w.extend(a)
shuffle(w)
texte = [ ''.join(sample('     abcdefghijklmonopqrstuvwxyz',randint(1,7))) for i in xrange(40) ]
X = ''.join(texte[i]+str(w[i]) for i in xrange(40))


# Searching the multiples of 48 in the chain X
def mult48(match):
    g1 = match.group()
    if int(g1)%48==0:
        return ( g1, X[0:match.end()] )
    else:
        return ( g1, 'not multiple')

for match in re.finditer('\d+',X):
    print '%s  %s\n' % mult48(match)

Answer 6

Any multiple is difficult, but here's a (python-style) regexp that matches the first 200 multiples of 48.

0$|1(?:0(?:08$|56$)|1(?:04$|52$)|2(?:00$|48$|96$)|3(?:44$|92$)|4(?:4(?:$|0$)|88$\
)|5(?:36$|84$)|6(?:32$|80$)|7(?:28$|76$)|8(?:24$|72$)|9(?:2(?:$|0$)|68$))|2(?:0(\
?:16$|64$)|1(?:12$|60$)|2(?:08$|56$)|3(?:04$|52$)|4(?:0(?:$|0$)|48$|96$)|5(?:44$\
|92$)|6(?:40$|88$)|7(?:36$|84$)|8(?:32$|8(?:$|0$))|9(?:28$|76$))|3(?:0(?:24$|72$\
)|1(?:20$|68$)|2(?:16$|64$)|3(?:12$|6(?:$|0$))|4(?:08$|56$)|5(?:04$|52$)|6(?:00$\
|48$|96$)|7(?:44$|92$)|8(?:4(?:$|0$)|88$)|9(?:36$|84$))|4(?:0(?:32$|80$)|1(?:28$\
|76$)|2(?:24$|72$)|3(?:2(?:$|0$)|68$)|4(?:16$|64$)|5(?:12$|60$)|6(?:08$|56$)|7(?\
:04$|52$)|8(?:$|0(?:$|0$)|48$|96$)|9(?:44$|92$))|5(?:0(?:40$|88$)|1(?:36$|84$)|2\
(?:32$|8(?:$|0$))|3(?:28$|76$)|4(?:24$|72$)|5(?:20$|68$)|6(?:16$|64$)|7(?:12$|6(\
?:$|0$))|8(?:08$|56$)|9(?:04$|52$))|6(?:0(?:00$|48$|96$)|1(?:44$|92$)|2(?:4(?:$|\
0$)|88$)|3(?:36$|84$)|4(?:32$|80$)|5(?:28$|76$)|6(?:24$|72$)|7(?:2(?:$|0$)|68$)|\
8(?:16$|64$)|9(?:12$|60$))|7(?:0(?:08$|56$)|1(?:04$|52$)|2(?:0(?:$|0$)|48$|96$)|\
3(?:44$|92$)|4(?:40$|88$)|5(?:36$|84$)|6(?:32$|8(?:$|0$))|7(?:28$|76$)|8(?:24$|7\
2$)|9(?:20$|68$))|8(?:0(?:16$|64$)|1(?:12$|6(?:$|0$))|2(?:08$|56$)|3(?:04$|52$)|\
4(?:00$|48$|96$)|5(?:44$|92$)|6(?:4(?:$|0$)|88$)|7(?:36$|84$)|8(?:32$|80$)|9(?:2\
8$|76$))|9(?:0(?:24$|72$)|1(?:2(?:$|0$)|68$)|2(?:16$|64$)|3(?:12$|60$)|4(?:08$|5\
6$)|5(?:04$|52$)|6(?:$|0$))