|
> multiples of 9, which will be the case for any number obtained by adding a set of numbers which together contain all and only the digits 142857 So that, then, is the fascinating root observation: that any series of decimal number made from these digits is a multiple of nine. What this means is that we can choose six random powers of 10 between 100 and 105 and make vector out of them, for instance <1, 100, 10, 10, 100000, 1000>. Then we do a dot-product between this and the vector <1, 4, 2, 8, 5, 7>. The result will be a multiple of 9. If we choose the vector as <1, 1, 1, 1, 1, 1> we get the straight sum of the digits. If we choose <100000, 10000, 1000, 100, 10, 1> we get 142857, and so on. Here is why it works: 10**<whatever> x == x (mod 9).
That is to say, any integer x is congruent, modulo 9, to a power of 10 times that integer.For instance 4 mod 9 == 4. 40 mod 9 == 4. 400 mod 9 == 4. And the reason for that is that 10 is 9 + 1; i.e. 10 is congruent to 1 modulo 9. So we are really multiplying by 1 under the congruence. So the choices of powers of ten in the coefficient vector do not matter. It works in other bases. For instance if any integer x is multiplied by a power of 6, that is congruent to x, modulo 5: $ clisp -q
[1]> (mod (* 2) 5)
2
[2]> (mod (* 6 2) 5)
2
[3]> (mod (* 6 6 2) 5)
2
[4]> (mod (* 6 6 6 2) 5)
2
Elementary number theory, my dear Watson.Okay, I now wrapped my hackerly head around this enough that I can garbage collect it away as fairly uninteresting. :) But, one more thing: what is special about 1, 4, 2, 8, 5, 7 in connection to 9? Why, they are relatively prime to 9. The remaining three positive residues in the mod 9 congruence are not: 0, 3 and 6. See here: https://en.wikipedia.org/wiki/Euler%27s_totient_function Euler's totient function phi counts the number of such integers. phi(9) == 6 (there are six of these numbers for 9). The above page even uses this very example. 1, 4, 2, 8, 5, 7 comprise the multiplicative group of integers modulo 9. https://en.wikipedia.org/wiki/Multiplicative_group_of_intege... |
For instance, D+E+A+D+B+E+E+F=104₁₀ which is not divisible by 5, but that indicates that (DEADBEEF+1) will be divisible by 5, which is correct.
We're also used to the "final digit test" for divisibility in base 10, which works for 1 (trivially), 2, 5, and 10; and indeed it works for a digit d in a base b if d divides b. Ternary has a digital-root test to determine whether a number is even (as in all odd bases, you can't use the final digit alone to answer that question). For example, 1202112₃ is odd because 1+2+0+2+1+1+2 is odd.
(Edit: deleted a spurious claim about hexadecimal divisibility tests.)