3 ms·
This exact state machine -- divisibility by 7 -- is one of my favorite state machines ever! It was a homework problem in college, and one of the few that stuck
by dahart 11y ago
This exact state machine -- divisibility by 7 -- is one of my favorite state machines ever! It was a homework problem in college, and one of the few that stuck with me over the years.
The implication of a DFA for divisibility by 7 is that it's easy (with practice) to figure divisibility by 7 in your head for arbitrarily long numbers as fast as someone can say them. Nice party trick! ;) I've also been having debates with people about whether divisibility testing in your head is a simpler operation than long division in your head. When you break it down carefully, long division in your head for a single digit divisor is very similar, and also surprisingly easy to do, the main difference might be simply having to remember quotient digits, and nothing more.
I'm curious where the DFA for divisibility by 7 might have originally come from, but I'm pretty sure it was a homework problem in the text I used, "Elements of the theory of Computation" by Lewis and Papdimitriou, Prentice Hall, 1981.