**mathematics**and found a problem that I thought was interesting, but couldn't figure out right away. So instead of looking at the answer, I decided to go to bed to see if (1) I couldn't sleep because my mind would keep working on the problem, or (2) I would dream of the answer in my sleep.

Well, neither happened, but I had kind of an odd dream. I was back in high school, but the room I was in looked like one of the junior high school rooms. I was doing a math problem on the blackboard. When I finished, a guy who was on the math team came over to me and said, "You should be on the math team." I replied, "I can't, because I'm 43 years old. I'm not even in high school." The dream shifted a bit afterwards to another part of the room where some people had science projects. One of them consisted of geometric 3D shapes with small black balls at their centers (imagine for example clear pyramids). It has been many years since I've taken chemistry, so if these were some kind of carbon molecules, I had no idea what they were. Anyway, one of the projects was left on the floor, so I went over to look at it. The project was making a strange sound and giving off smoke like there was some type of electrical short in it. However, that didn't make sense because the project wasn't attached to or powered by anything. That was the end of the dream.

I was feeling bummed because I didn't figure out the math problem completely, so I cheered myself up a bit by solving a similar (easier) problem (designing a finite state automaton that halts iff the input is divisible by 4).

- Current Mood: discontent

## Comments

likablenerdEssentially we need to do this on a digit-per-digit basis, so it makes sense to look at things, well, a digit at a time:

So let's say our original number is x

Define r_n = x_n % 3.

x_0 = d_0.

x_n = x_(n-1)*2 + d_n

Then consider d_n, r_n with respect to r_(n-1). It's natural to consider r_n (the remainder of x_n divided by 3) since we want this to equal zero.

If r_(n-1) = 0 then:

If d_n = 0, r_n = 0.

If d_n = 1, r_n = 1.

If r_(n-1) = 1 then

If d_n = 0, r_n = 1.

If d_n = 1, r_n = 0.

If r_(n-1) = 2 then

If d_n = 0, r_n = 1.

If d_n = 1, r_n = 2.

Took me about an hour and a half to get unconfused. Anyway, so you can see that there should be three states.

This problem is basically about algebra / number theory (arithmetic modulo n).

likablenerd