News for hackers. Stuff that matters.
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.

  N = 2

  | state | 0 | 1 |
  |-------+---+---|
  |     0 | 0 | 1 |
  |     1 | 0 | 1 |

  N = 3

  | state | 0 | 1 |
  |-------+---+---|
  |     0 | 0 | 1 |
  |     1 | 2 | 0 |
  |     2 | 1 | 2 |

  N = 4

  | state | 0 | 1 |
  |-------+---+---|
  |     0 | 0 | 1 |
  |     1 | 2 | 3 |
  |     2 | 0 | 1 |
  |     3 | 2 | 3 |
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.

There are no comments on this comment yet.