P. Gács and L. Lovász: Complexity of Algorithms

A Pretty good book in English (the Hungarian version is available as well). This book is a must-have read for everybody who would like to focus on programming and AI development.

The book's first edition was written at Yale University as lecture notes in 1999.

The second chapter is about the finite automata, and there is an interesting exercise:

Exercise 2.2.2 Construct a finite automaton with as few states as possible that receives the digits of an integer in decimal notation, starting from the left and

(a) the last output is one if the number is divisible by three and zero if it is not.

(b) the same for divisibility by 7.

Let's focus on exercise (b) now; here is a Python code which brings us closer to the solution:

https://en.wikipedia.org/wiki/Modular_arithmetic

import random

def mod7(s):
    first_digit= int(s[0])
    state = first_digit-7 if first_digit >= 7 else first_digit
    diff= [0, 3, 6, 2, 5, 1, 4, 0, 3, 6] # i*10%7 where i = 0..9

    for c in s[1:]:
        i = int(c)
        i = i - 7 if i>=7 else i
        i = i + diff[state]
        state = i-7 if i>=7 else i 
        
    return state;
      
def test_mod7():   
    for i in range(100000):
        n = random.randint(1000000,1000000000)
        calculated = mod7(str(n))
        original = n%7
        if (original != calculated):
            print("!ERROR at number:{} modulo 7 correct:{} calculated:{}".format(n, original, calculated))\

test_mod7()