The author constructs his regular expression ad hoc, by trying examples and spotting patterns. His proof that it's correct consists of trying it for the first 5000 non-negative integers. Here's a more principled approach for those who prefer to know that, why, and how something works.<p>I'll use "@" instead of the usual asterisk to denote "repeated zero or more times" to avoid HN formatting issues.<p>First, let's construct a finite state machine that does the job. It needs three states, one for each value the number-so-far might have mod 3. You can pretty much write this down immediately. State 0 goes to itself on seeing a 0, and to state 1 on seeing a 1. State 1 goes to state 2 on seeing a 0, and to state 0 on seeing a 1. State 2 goes to state 1 on seeing a 0, and to itself on seeing a 1.<p>Now, there's a general technique for converting an FSM to a regular expression. The idea is that you label edges with regular expressions and not just single symbols. Then you eliminate states one by one, until you're left with only the start state and the accepting end state. To eliminate a state y, consider all x,z such that there are transitions x -> y -> z; replace y and those transitions with a bunch of transitions straight from x to z, of the form [what it takes to go x -> y] [what it takes to go y -> y]@ [what it takes to go y -> z]. Repeat. (When you get multiple edges from one state to another, use the | operator.) Eventually you just have a start state and an end state, and then the label on the edge from one to the other is the RE you need. Unless the start and end states are the same, in which case you need to allow arbitrary repetitions of that RE, so add another star.<p>OK. So now we eliminate state 2. It happens that the only edge we need to add goes 1 -> 1, and it's labelled 01@0. In other words: if you have something that's 1 mod 3, then the bit-sequences that take you back to 1 mod 3 while visiting only {1 mod 3, 2 mod 3} are those of the form: 0, maybe some 1s, 0.<p>So now we have states 0 and 1, with transitions 0 -> 0 (labelled 0), 0 -> 1 and 1 -> 0 (both labelled 1), and 1 -> 1 (labelled 01@0). State 0 is both the start state and the accepting end state.<p>And now we eliminate state 1. In just the same way, the only edge we need to add goes 0 -> 0, and it's labelled ... well, we have 0 -> 1 [1], then zero or more of 1 -> 1 [01@0], then 1 -> 0 [1]. In other words: 1(01@0)@1.<p>So now we have only one state, which has the 0 -> 0 transition labelled 0 that it always had, plus a new one, labelled 1(01@0)@1. That's equivalent to a single transition 0 -> 0, labelled 0|1(01@0)@1. So, finally, our RE is obtained by starring that: (0|1(01@0)@1)@. Where, to repeat, "@" means what's usually denoted by an asterisk.<p>This RE is actually simpler than Alex's: fewer characters and fewer stars. I don't know which will execute faster in a typical RE engine.<p>[EDITED to fix asterisk screwage -- I had no idea that HN italicization works across paragraphs -- and to add: while I was writing this, <i>qntm</i> made a similar comment. Except that I think constructing the FSM is trivial and converting it to an RE is nontrivial, whereas <i>qntm</i> thinks constructing the FSM is nontrivial and converting it to an RE is trivial. Hopefully the combination of <i>qntm</i>'s comments and mine will make everything clear.]