Hacker News Reader

So, all of your original sum numbers (999, 99, 27, 1485, 2871, and 42858) are themselves 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. That means a lot of other "also" additions will work out too! You can even change the order, like 578 + 214 = 792 (a multiple of 9, and hence the digital root will end up being 9). Any order and any choice of how to break the numbers will work, because of the digital root property (and, importantly, the rule that "The digital root of a + b is congruent with the sum of the digital root of a and the digital root of b modulo 9").

Try this fun Python program to see how multiples of 9 are always generated no matter how you combine the digits:

  #!/usr/bin/env python
  
  import random
  
  digits = [1, 4, 2, 8, 5, 7]
  
  for times in range(20):
      digits_left = digits[:]
      nums = []
      while digits_left:
         this_num = 0
         for i in range(random.randint(1, len(digits_left))):
             digit = random.choice(digits_left)
             this_num *= 10
             this_num += digit
             digits_left.remove(digit)
         nums.append(this_num)
      print " + ".join(map(str, nums)), "=", sum(nums), "(a multiple of 9)"

Sample output:

  4271 + 58 = 4329 (a multiple of 9)
  7412 + 58 = 7470 (a multiple of 9)
  8 + 124 + 5 + 7 = 144 (a multiple of 9)
  845127 = 845127 (a multiple of 9)
  147285 = 147285 (a multiple of 9)
  1 + 824 + 75 = 900 (a multiple of 9)
  5 + 2 + 481 + 7 = 495 (a multiple of 9)
  758 + 41 + 2 = 801 (a multiple of 9)
  47125 + 8 = 47133 (a multiple of 9)
  7584 + 12 = 7596 (a multiple of 9)
  1275 + 8 + 4 = 1287 (a multiple of 9)
  475 + 12 + 8 = 495 (a multiple of 9)
  12 + 5 + 478 = 495 (a multiple of 9)
  4251 + 7 + 8 = 4266 (a multiple of 9)
  185 + 274 = 459 (a multiple of 9)
  28514 + 7 = 28521 (a multiple of 9)
  41278 + 5 = 41283 (a multiple of 9)
  457182 = 457182 (a multiple of 9)
  845712 = 845712 (a multiple of 9)
  2718 + 54 = 2772 (a multiple of 9)

> 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...

The "other bases" issue, which you come to right at the end, fascinated me in middle school: for the reasons you describe, digital root tests for divisibility by a digit d work in any base b if d divides (b-1). For example, in hexadecimal there is a digital root test for divisibility by 1 (trivially), 3, 5, or 15 in hexadecimal.

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.)

I figured we all learned this from Square One: https://www.youtube.com/watch?v=Q53GmMCqmAM

you forgot

14285 + 7 = 14292; 1+4+2+9+2 = 18; 1+8 = 9

Reply on news.ycombinator.com