CODEWITHSUNDEEP
regexbinarydivision
The Beast
The Beast

Reputation: 1669

Regular Expression for Binary Numbers Divisible by 5

I want to write a regular expression for Binary Numbers Divisible by 5.
I have already done the regular expressions for Binary Numbers Divisible by 2 and for 3 but I couldn't find one for 5.

Any suggestions?

Upvotes: 14

Views: 25223

Answers (3)

leofun01
leofun01

Reputation: 235

For non empty binary sequence divisible by 5 you can use [probably the shortest] explicit regex :

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

If you want to use it in some programming language and your environment allows to make replacement { 0->1, 1->0 } then you can make your code shorter because in correctly formed regex there always exist reversed common part :

 (0| 1(10)*(0|11) \
(01* 0(01)*(1|00) )*1)+
     ^-^^---^-^^-       xor 1

(here spaces used for highlighting only)

The existence of reversible common part caused by the symmetry of every odd graph regex-div-5-init.png

This graph was built using the table of remainders :

from #     : 0 1 2 3 4
to 2*# + 0 : 0 2 4 1 3  mod 5
to 2*# + 1 : 1 3 0 2 4  mod 5
         |   ^-^-^-^-^- vertices
       edges

For non empty binary sequences divisible by (5 * 2^N) you can use this pattern :

^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0*)$    : divisible by  5
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+00*)$   : divisible by 10
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+000*)$  : divisible by 20
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0{3,})$ : divisible by 40
^(0+|(0*1(10)*(0|11)(01*0(01)*(1|00))*1)+0{4,})$ : divisible by 80, and so on ...

Upvotes: 0

Ferit
Ferit

Reputation: 9727

2^0 =  1 =  1 mod 5
2^1 =  2 =  2 mod 5
2^2 =  4 = -1 mod 5
2^3 =  8 = -2 mod 5
2^4 = 16 =  1 mod 5
2^5 = 32 =  2 mod 5
   ...     -1 mod 5
   ...     -2 mod 5

So we have a 1, 2, -1, -2 pattern. There are two subpatterns where only the sign of the number alternates: Let n is the digit number and the number of the least significant digit is 0; odd pattern is

(-1)^(n)

and even pattern is

2x((-1)^(n))

So, how to use this?

Let the original number be 100011, divide the numbers digits into two parts, even and odd. Sum each parts digits separately. Multiply sum of the odd digits by 2. Now, if the result is divisible by sum of the even digits, then the original number is divisible by 5, else it is not divisible. Example:

100011
1_0_1_ 1+0+1 = 2
_0_0_1 0+0+1 = 1; 1x2 = 2

2 mod(2) equals 0? Yes. Therefore, original number is divisible.

How to apply it within a regex? Using callout functions within a regex it can be applied. Callouts provide a means of temporarily passing control to the script in the middle of regular expression pattern matching.

However, ndn's answer is more appropriate and easier, therefore I recommend to use his answer.

Upvotes: 2

ndnenkov
ndnenkov

Reputation: 36110

(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*

Add ^$ to test it with regexp. See it working here.

You can build a DFA and convert it to regular expression. The DFA was already built in another answer. You can read it, it is very well explained.
The general idea is to remove nodes, adding edges. before

Becomes:

after

Using this transformation and the DFA from the answer I linked, here are the steps to get the regular expression:
(EDIT: Note that the labels "Q3" and "Q4" have been mistakenly swapped in the diagram. These states represent the remainder after modulus 5.) step1 step2 step3 step4 step5

Upvotes: 33

Related Questions