Instead of remembering the weighted sequence, you can also compute it implicitly as you go (when reading the number from left to right). Example:

    8
    ^ 8 (mod 7) is 1, remember that
    85
     ^ 1 · 10 (mod 7) is 3, and 3 + 5 (mod 7) is 1, remember that
    853
      ^ 1 · 10 + 3 (mod 7) is 6
    8536
       ^ 6 · 10 + 6 (mod 7) is 3
    85362
        ^ 3 · 10 + 2 (mod 7) is 4
    853629
         ^ 4 · 10 + 9 (mod 7) is 0

Hence 853629 (mod 7) = 0 and it is divisible by 7. The corresponding code would be

    def modulo(number, k):
        val = 0;
        for digit in str(number):
            val = (val * 10 + int(digit)) % k
        return val

Of course, you can apply the modulo within the intermediate calculations as well, so instead of multiplying by 10 you can e.g. multiply by 3 = 10 (mod 7) instead. The key idea is that you can go from one weight to the next by multiplying with 10 (mod 7), so if you sum some weighted digits you can update all the weights at once with a simple multiplication.

The advantage is that you only need a small amount of memory (a single number between 0 and 6), so this is a kind of general divisibility rule where you only have to do small calculations in your head.

If I may digress a bit into automata theory, this means that you can construct a finite state automaton that determines whether a number is divisible by 7 (or any other constant) by reading its digits from left to right. Additionally, if a finite state automaton can do something reading from left to right, there is another automaton doing the same thing but reading from right to left. This means that there is also a 'simple' divisibility rule when starting with the least significant digit, though it may be a bit harder to find.

Mind. Blown.

This is basically what also happens during long division! I marked the remainder of the previous operation in each line with a bracket (no italics in code formatting, sadly), appending another digit of the dividend behind them is the same operation as multiplying the 'remembered' number by 10 and adding the next digit to it:

    8 5 3 6 2 9  /  7  =  1 2 1 9 4 7; remainder 0
  - 7                       
   --                       
   [1]5            How long division works:
  - 1 4   <-------     subtract largest possible multiple,     
   ----                 note remainder in next line, append
     [1]3               next digit from number at top, and 
    -   7               repeat until done. And make sure to
     ----               keep track of the result.
       [6]6
      - 6 3                 
       ----                 
         [3]2
        - 2 8
         ----
           [4]9
          - 4 9
           ----
             [0]  <= final remainder = 0, i.e. 7 is a divisor of the number

Thanks a lot for your comment, this was insightful!

I never thought about that! That definitely is an interesting connection.

This is essentially Horner's method for calculating the value of a polynomial. [1]

In your example, you calculate the value of the polynomial 8x^5+5x^4+3x^3+6x^2+2x^1+9 with x=10. The value is 853629, of course, but it you perform your calculation modulo 7, you have precisely followed Horner's method in the field F_7. To further simplify the calculation, note (as you did!) that 10 is congruent to 3 mod 7, so use x=3 instead of x=10.

[1] https://en.wikipedia.org/wiki/Horner's_method

That's much easier than the (separate) div 7 rule that this blog post links to: https://www.johndcook.com/blog/2010/10/27/divisibility-by-7/

Maybe not mechanically easier, but easier to remember.

Woah. That's very elegant and simple.

Interesting. I'll translate this bit from the entry:

One can also find periodical sequences for other natural numbers. E.g.,

* for 11, the sequence +1, -1, ...

* for 13, the sequence 1, -3, -4, -1, 3, 4, ...

For most divisors, it is not practical to test divisibility this way, as there are only few easily remembered weight sequences.

I came in the comments section with the intent of asking HN about generalized divisibility rules for any number N with any base B. Looks like you provided the goods.

You are welcome, I am glad I could help :)