Re:Divisibility by 7 is a Walk on a Graph (2009)
by Jtsummers on Sunday November 08, 2015 @10:38PM
(#10531252)
My variation of this requires the input number (I) to be in binary,
and read from leftmost digit to the right (most significant to least
significant). Here's the table version of N = 2 through N = 4.
Each state represents a potential result of I mod
N. Constructing it becomes mechanical, as in each state you can either
double it (input digit D = 0) or double it + 1 (input digit D = 1). So
in N = 4, determining the outputs of state 2: You can double it, and 4
mod 4 = 0, therefore the next state is 0; You can double it + 1, and 5
mod 4 = 1, therefore teh next state is 1.
As to making this particular style graph, I'm currently playing around
with it.
EDIT: Hmm, left something out. You can convert this to any base, you just end up with more transitions out of each state (for a base B, you need B transitions).
EDIT Again: omaranto has it correct for generating the article's style of graphs. Guess I should've refreshed before posting, but working it out myself was fun and successfully kept me from sleeping.
As to making this particular style graph, I'm currently playing around with it.
EDIT: Hmm, left something out. You can convert this to any base, you just end up with more transitions out of each state (for a base B, you need B transitions).
EDIT Again: omaranto has it correct for generating the article's style of graphs. Guess I should've refreshed before posting, but working it out myself was fun and successfully kept me from sleeping.