4 ms·

Can we build such state diagrams to check divisibility by other digits too?

omaranto 11y ago
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.)
zodiac 11y ago
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
Jtsummers 11y ago
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.

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.)

zodiac 11y ago

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

Jtsummers 11y ago

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.