I was bored during lockdown, so I decided to start a blog about my random thoughts about math. It contains some solutions to math problems, and some 'simple' applications of math.
Saturday 30 October 2021
Magic 7 finite state machine
Consider the riddle in the following video
You can solve it as follows:
You can write any number as
$$x = \overline{x_nx_{n-1}...x_1x_0}$$
With the overline meaning concatenation, and $x_i$, the different digits of $x$.
This notation is a shorthand for
$$x = \sum 10^i x_i$$
We can rewrite this sum using distributivity to be
$$ x = x_0 + 10(x_1 + 10(x_2 + ... )))$$
If we define our instuction $f_{x_i}$ as
$$f_{x_i}(a) = x_i + 10a$$
Then $x$ can be written as
$$ x = f_{x_0}(f_{x_1}(f_{x_2}( ... ))) $$
or
$$ x = f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}(x_n) $$
But as $f_{x_n}(0) = x_n$, it is more natural to write it as
$$ x = f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}\odot f_{x_n}(0) $$
We are only interested in whether or final result is a multiple of 7, ans as we only use multiplication and addition, we can consider the the full system in mod 7.
$$ x \equiv f_{x_0} \circ f_{x_1} \circ ... \circ f_{x_{n-1}}\circ f_{x_n}(0) (\mod 7)$$
This formula now represents a finite state machine with 7 states, (0,1,2,3,4,5 and 6) and 10 instructions ($f_0$ to $f_9$), where the final state is the same a s the remainder of the original number when dividing by 7.
0
1
2
3
4
5
6
0
0
3
6
2
5
1
4
1
1
4
0
3
6
2
5
2
2
5
1
4
0
3
6
3
3
6
2
5
1
4
0
4
4
0
3
6
2
5
1
5
5
1
4
0
3
6
2
6
6
2
5
1
4
0
3
7
0
3
6
2
5
1
4
8
1
4
0
3
6
2
5
9
2
5
1
4
0
3
6
Now, if we call state 0 X, state 1 A, state 2 C, state 3 F, state 4 B, state 5 D and state 6 E, we arrive at the transition table given by the riddle. So by consequence, the transition table works as a division test by 7.