3 ms·
I had some fun reverse engineering that. Here is my take at how it works. Label all of the nodes 0 through 6, starting with making the white node 0, and follow
by gizmo686 11y ago
I had some fun reverse engineering that. Here is my take at how it works.
Label all of the nodes 0 through 6, starting with making the white node 0, and following the black arrows. We can consider each of these nodes to represent a congruence mod 7.
Let n be the first digit of the number, and nXXX be the entire number. After we walk n nodes by following the black arrows, we arrive at the node n' = n MOD 7. Notice that n'XXX = nXXX MOD 7. More specifically, nXXX is divisible mod 7 if and only if n'XXX is divisible by 7.
Let m be the second digit. At this point, we reduced the problem to testing n'mXX MOD 7. Notice that n'mXXX = (10n' + m)XX. [0] Notice that following the white arrow at an arbitrary node, k, is equivilent to following 10k black arrows. [1] This means that after following the white arrow, we have reduced the problem to mXX. At this point, we simply recurse to the first step until we are out of digits.
[0] This construction is slightly improper, in that it involves a single "digit" having a value greater than 10.
[1] This can be verified by considering the value of 10k MOD 7, and comparing it with the destination node.