0

So if I understand correctly I need to make a graph with q nodes, but to me the algorithm of divisibility with 7 is way to complex, let alone having 1 remainder. Any help?

Nikos Gavra
  • 1
  • You don't need to divide by $7$, you are only after the remainder, not the quotient. Reading from left to right may be an issue though...do you know how many digits there are at the start? – lulu Oct 21 '18 at 18:26
  • So how do I approach it? – Nikos Gavra Oct 21 '18 at 18:27
  • 1
    Well, if you were reading from right to left you just keep track of the residues. So if your number were $\cdots 35$ you start with $5$, then you know that $3\times 10^1\equiv 2 \pmod 7$ so you'd add $2$ to $5$ to get $0\pmod 7$ as the running sum. Not immediately sure how you do it if you start at the other end without knowing the length. – lulu Oct 21 '18 at 18:30
  • 2
    The same can be done when reading from left to right. Start with $3$, (remainder: $3$) then read $5$: Multiply previous remainder with $3$ as $10 \equiv 3 \pmod 7$ and add $5$: $3\times3+5=14 \equiv 0 \pmod 3$. – Ingix Oct 21 '18 at 18:34
  • @Ingix Oh, very good. Yes, you are right. – lulu Oct 21 '18 at 18:34

1 Answers1

0

Going along the same lines as Ingix points out in the question's comments, there is a way to handle this properly without needing full division.

First, write a recursive program to solve the problem a digit at a time:

machine :: State -> [Digit] -> Result
machine 1     []     = Accept
machine _     []     = Reject
machine state (d:ds) = machine ((10*state + d) `mod` 7) ds

For the input 1286, this will be called as:

machine 0 [1, 2, 8, 6]

During processing of digits, there will be seven states from zero to six. The machine will start at state zero.

We can see that if there's no input remaining, state one is the only state that should accept. All others should reject.

If there is input remaining, the states can be wired to each other with the formula in the last line of the program above: $ state \to 10 state + digit \mbox{, reduced modulo } 7 $.

State transition table

Here's part of the state transition table:

┏━━━━━━┯━━━━━━━━━━━━━━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┳━━━┓
┃ Input ╲ Initial state ┃ 0 ┃ 1 ┃ 2 ┃ 3 ┃ 4 ┃ 5 ┃ 6 ┃
┣━━━━━━━━┷━━━━━━━━━━━━━━╋━━━╇━━━╇━━━╇━━━╇━━━╇━━━╇━━━┫
┃     End of input      ┃ R │ A │ R │ R │ R │ R │ R ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           0           ┃ 0 │ 3 │ 6 │ 2 │ 5 │ 1 │ 4 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           1           ┃ 1 │ 4 │ 0 │ 3 │ 6 │ 2 │ 5 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           2           ┃ 2 │ 5 │ 1 │ 4 │ 0 │ 3 │ 6 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┋                       ┋   ┊   ┊   ┊   ┊   ┊   ┊   ┋
┣━━━━━━━━━━━━━━━━━━━━━━━╉───┼───┼───┼───┼───┼───┼───┨
┃           9           ┃ 2 │ 5 │ 1 │ 4 │ 0 │ 3 │ 6 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┻━━━┛

There are many patterns in it that make filling it out easier.

Chai T. Rex
  • 299