Regex filter numbers divisible by 3

Question

I have a list of comma-separated ids(digits) . And I need to get only these which are divisible by 3.

Example: i = "3454353, 4354353, 345352, 2343242, 2343242 ..."

regex is useful for matching patterns against strings. Not for doing math. It would be much easier to just split your string by commas and then filter the resulting list on the divisible by 3 condition. — Paul, Jun 12 '12 at 07:36
Please post more information, such as an example input and output. — jamylak, Jun 12 '12 at 07:41
[Regex to match binary numbers divisible by 3](http://stackoverflow.com/questions/867279/regular-expression-to-define-some-binary-sequence) could be of interest. — Qtax, Jun 12 '12 at 07:43
I'm sure this one is tagged `regex` just by mistake, however it would be interesting to find a regex solution, if it exists. — georg, Jun 12 '12 at 07:46
@thg435A regex solution isn't that hard to come up with since the sum of the digits of a number divisible by 3 is also divisible by three. You need three states in a DFA, a state for remainder 0, 1, and 2. and remainder 0 is the accept state. — Paul, Jun 12 '12 at 07:50
I also wondered if there's such but as ascii-lime said. Maybe regex is not good at maths — Martin, Jun 12 '12 at 07:52
rel: http://stackoverflow.com/questions/2430556/regular-expression-for-any-number-divisible-by-60-using-c-sharp-net/3694683#3694683 — georg, Jun 12 '12 at 08:11

Tim Pietzcker · Answer 1 · 2012-06-12T08:14:03.687

13

Just for the heck of it:

reobj = re.compile(
    r"""\b            # Start of number
    (?:               # Either match...
     [0369]+          # a string of digits 0369
    |                 # or
     [147]            # 1, 4 or 7
     (?:              # followed by
      [0369]*[147]    # optional 0369s and one 1, 4 or 7
      [0369]*[258]    # optional 0369s and one 2, 4 or 8
     )*               # zero or more times,
     (?:              # followed by
      [0369]*[258]    # optional 0369s and exactly one 2, 5 or 8
     |                # or
      [0369]*[147]    # two more 1s, 4s or 7s, with optional 0369s in-between.
      [0369]*[147]
     )
    |                 # or the same thing, just the other way around,
     [258]            # this time starting with a 2, 5 or 8
     (?:
      [0369]*[258]
      [0369]*[147]
     )*
     (?:
      [0369]*[147]
     |
      [0369]*[258]
      [0369]*[258]
     )
    )+                # Repeat this as needed
    \b                # until the end of the number.""", 
    re.VERBOSE)
result = reobj.findall(subject)

will find all numbers in a string that are divisible by 3.

edited Jun 12 '12 at 08:14

answered Jun 12 '12 at 07:52

Tim Pietzcker

328,213
58
503
561

that's more accurate answer thanks again, @Tim Pietzcker would you please provide us a bit information of how it works? – Martin Jun 12 '12 at 07:58
@Martin: I hope you're not going to use that in production code. Regex is not the right tool for this, even if it works. This is horribly inefficient. – Tim Pietzcker Jun 12 '12 at 08:00
Does not match 222, 555, etc. 555/3=185 . 222/3=74. `[258]` block is never alone. – Kobi Jun 12 '12 at 08:00
@Kobi: My edited version does. But thg435 is right - there's still something missing. See - that's why regex is not the right tool for this. Will need to test a bit more to at least get this correct... – Tim Pietzcker Jun 12 '12 at 08:02
4

I've seen one that seems to work (spoiler, I guess): http://www.rubular.com/r/ZcRDblHg8M – Kobi Jun 12 '12 at 08:04
Forgot my source: http://stackoverflow.com/a/3694683/7586 (Mark adds some checks for `% 60`, but I removed them) . I have also done it with the .Net stack: http://wp.me/phMG2-4I – Kobi Jun 12 '12 at 08:14
@Kobi: Thanks. I have taken the liberty to use this regex you linked to and comment it here - it's not mine, so I can't take the credit for it (and as I said, I still don't think regexes should be used for this), but that's better than leaving my original (incomplete and incorrect) regex standing here (the old one can be found in the revision history, of course). – Tim Pietzcker Jun 12 '12 at 08:16
2

A DFA converts to the slightly simpler regex `([0369]|([147][0369]*[258])|(([258]|[147][0369]*[147])([0369]*|[258][0369]*[147])([147]|[258][0369]*[258])))*`: http://tinyurl.com/7trrs5j – Paul Jun 13 '12 at 06:29
Paulpro's simplified regex above does not work for all cases, unfortunately. E.G. 390259107 not matched. – Tim Radcliffe Jan 14 '14 at 14:38
The one in the answer works for too many cases, e.g. 1111 and 2222 *match* and should not – Sam Howard Dec 21 '20 at 03:11
1

@MichaelBoger: No, it doesn't - check it out on https://regex101.com/r/ipsFSQ/1 – Tim Pietzcker Dec 24 '20 at 08:43
@TimPietzcker Oh, I see where I got confused; the ?: parts are broken onto lines and I thought it was a "match either" rather than "match both in succession', probably due to the comment on line 3. My apologies! – Sam Howard Dec 25 '20 at 09:29

score 9 · Accepted Answer · answered Jun 12 '12 at 07:39

9

If you really mean digits (not numbers), this is as easy as

 re.findall(r'[369]', my_str)

For a list of numbers, it's quite easy without regular expressions:

lst = "55,62,12,72,55"
print [x for x in lst.split(',') if int(x) % 3 == 0]

answered Jun 12 '12 at 07:39

georg

211,518
52
313
390

7

Doesn't zero belong there? – eumiro Jun 12 '12 at 07:39
1

+1 to both thg435 for the answer and eumiro since 0 is indeed divisible by any non-zero integer. – Paul Jun 12 '12 at 07:45
Also you may need to split on `, ` (comma space), not just `,` as per the recent edit to the question. – Paul Jun 12 '12 at 07:46
Despite the second example isn't regex, it met my needs. 10x – Martin Jun 12 '12 at 07:49
2

@Martin, you probably shouldn't use "*10x*", at least math.stackexchange.com, unless you want to confuse people. – Qtax Jun 12 '12 at 08:03
1

@Martin - A suggestion: as much as I love regular expressions, and I do, this is definitely the better answer, and you should accept it if you can avoid a regex. – Kobi Jun 12 '12 at 08:22

score 3 · Answer 3 · edited Jan 26 '23 at 14:58

3

A hopefully complete version, from reduction of DEA[1]:

^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258])))+$

[1:] Converting Deterministic Finite Automata to Regular Expressions', C. Neumann 2005
NOTE: There is a typo in Fig.4: the transition from q_j to itself should read ce*b instead of ce*d.

edited Jan 26 '23 at 14:58

Pedro Gimeno

2,837
1
25
33

answered Jun 12 '14 at 23:35

merger

31
1

score 2 · Answer 4 · edited May 23 '17 at 11:56

2

Using the idea from this question i get:

i = "1, 2, 3, 4, 5, 6, 60, 61, 3454353, 4354353, 345352, 2343241, 2343243"

for value in i.split(','):
    result = re.search('^(1(01*0)*1|0)+$', bin(int(value))[2:])
    if result:
        print '{} is divisible by 3'.format(value)

But you don't want to use regular expressions for this task.

edited May 23 '17 at 11:56

Community

1
1

answered Jun 12 '12 at 08:02

Matthias

12,873
6
42
48

Regex filter numbers divisible by 3

4 Answers4

Linked