12

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?

CSᵠ
  • 10,049
  • 9
  • 41
  • 64
The Beast
  • 1,629
  • 2
  • 29
  • 42
  • Please show us what you've tried and how it's not working. – l'L'l Dec 26 '15 at 23:58
  • i don't really know where to start because the numbers are very differents : 0101 , 1010 , 1111 , 10100 ... there is no special rule to apply – The Beast Dec 27 '15 at 00:04
  • 2
    Generalized Pascal divisibility criteria gives reduce sequence of (1, 2, 4, 3, 1, ...) and I hardly can see how this can be utilized by regex. However, if your final goal is just to check huge binary number for divisibility, you can use it directly. Simply pass through your number from lowest digit multiplying digits on sequence numbers and collecting total. The remainder of total is the remainder of initial number. That's the best link I found so far http://mathworld.wolfram.com/DivisibilityTests.html – Vasily Liaskovsky Dec 27 '15 at 00:19
  • 2
    A regular expression is not the right tool for this job. – Raymond Chen Dec 27 '15 at 02:19
  • @VasilyLiaskovsky, this is a classical example of FDA/regular expression exercise. Check out my answer. – ndnenkov Dec 27 '15 at 14:58

3 Answers3

29
(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
davidlc
  • 113
  • 1
  • 5
ndnenkov
  • 35,425
  • 9
  • 72
  • 104
  • I would be very happy if your answer is correct. But if your answer is correct, why this isn't matching? https://regex101.com/r/hP1cO0/1 – Ferit Dec 27 '15 at 08:32
  • Found it why. OK. You are right, congrats! I'm very pleased to see your answer working, because I spent 3 hours for searching a regex, and disappointed as I thought there is no solution. – Ferit Dec 27 '15 at 08:35
  • This solution is fantastic.But just for a sake of technicality, the actual answer would be zero or more occurrence of the answer mentioned. Isn't that ? – Soumya Kanti Naskar May 06 '17 at 07:03
  • @SoumyaKantiNaskar, what do you mean. – ndnenkov May 06 '17 at 08:54
  • nice answer with the images. Kudos for that. Just one short comment after trying to decipher this logic myself from scratch: you seem to have the Q3 and Q4 state names mixed up in the starting image making it bit harder to follow (obviously that doesn't have any effect on the correct result - just makes it a bit harder to understand how the the starting situation is created). – ejuhjav Mar 20 '18 at 21:49
  • @ejuhjav mixed up as in relation to where the other answer left off? Sorry about that. Glad you liked it though. – ndnenkov Mar 21 '18 at 07:01
1
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.

Ferit
  • 8,692
  • 8
  • 34
  • 59
-1

However, "^(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))1)$" matches empty string.

user2742080
  • 41
  • 7