4 ms·
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
by suyjuris 6y ago
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.
- _Microft 6y agoMind. 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!
- suyjuris 6y agoI never thought about that! That definitely is an interesting connection.
- huhtenberg 6y agoWoah. That's very elegant and simple.
- kzrdude 6y agoThat'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/ https://www.johndcook.com/blog/2010/10/27/divisibility-by-7/ Maybe not mechanically easier, but easier to remember.
- hanche 6y agoThis 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 https://en.wikipedia.org/wiki/Horner's_method