5 ms·

You might also like weighted digit sums. I'll copy the example from german Wikipedia article [0] as you might generalize from that easier as when I would write

You might also like weighted digit sums. I'll copy the example from german Wikipedia article [0] as you might generalize from that easier as when I would write it down in mathematical notation: Here are the weights for 7: 1 ≡ 1 (mod 7) 10 ≡ 3 (mod 7) 100 ≡ 2 (mod 7) 1000 ≡ −1 (mod 7) 10000 ≡ −3 (mod 7) 100000 ≡ −2 (mod 7) 1000000 ≡ 1 (mod 7) ... 10^n ≡ a_n (mod 7) Then multiply the weights with the digit on the respective position and sum up. Repeat if you like. If the resulting number is divisible by 7, you know that the initial number also was. Example: 853629: 8x (-2) + 5x (-3) + 3x (-1) + 6x 2 + 2x 3 + 9x 1 = -16-15-3+12+6+9 = -7, therefore 853629 is divisible by 7. [0] https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme

tgv 6y ago
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.
- deleted 6y ago
  [deleted]
ddxxdd 6y ago
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.
- _Microft 6y ago
  You are welcome, I am glad I could help :)
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 ago
  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!

tgv 6y ago

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.

deleted 6y ago
[deleted]

ddxxdd 6y ago

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.

_Microft 6y ago
You are welcome, I am glad I could help :)

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 ago
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!