News for hackers. Stuff that matters.
Re:Divisibility by 7 is a Walk on a Graph (2009) by askbypollankit on Sunday November 08, 2015 @10:25PM (#10531209)
Can we build such state diagrams to check divisibility by other digits too?
Re:Divisibility by 7 is a Walk on a Graph (2009) by omaranto on Sunday November 08, 2015 @10:30PM (#10531225)
Yes, it's easy: to test divisibility by n make a graph with n verities labeled 0 through n-1; put black arrows from each vertex k to (k+1) mod n; and put white arrows from each k to 10k mod n.

(That's for testing divisibility by n of numbers written in base 10; for others bases just replace the 10 above.)

Re:Divisibility by 7 is a Walk on a Graph (2009) by zodiac on Sunday November 08, 2015 @10:32PM (#10531231)
Yup!

If we're trying to compute 3256 % 7 and we know that 325 % 7 = 3, then 3256 % 7 = (325 * 10 + 6) % 7 = (3 * 10 + 6)

Computing 10 % 7, 20 % 7 etc generates the white arrows.

I think unless we're checking divisibility by primes, though, the white and black arrows won't share edges

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.