Fun math algorithms

[Albert Chan]

(09-05-2020 10:31 PM)Han Wrote:  Dividing by 9
\[ \frac{3461}{9} = \frac{3\cdot 10^2 \cdot 9 + (3+4+1) \cdot 10 \cdot 9 + 4\cdot 9 + (4 + 1)}{9} =
3\cdot 10^2 + (3+4+1) \cdot 10 + 4+ \frac{4 + 1}{9}
\]

Great trick ! Doing it vertically, you can clearly see the advantage

3461 ÷ 9
 76       // 3+4=7
 13       // 7+6=13
  41      // 1+3=4
   5      // 4+1=5
---------
384 + 5/9

Another trick is to scale denominator to 1 - ε, 1/(1-ε) = 1 + ε + ε² + ...

\(\frac{3461}{9} = \frac{34610+3461}{99} = \frac{380.71}{1-0.01} = 380.71 + 3.8071 + \cdots = 384 + 5/9\)

\(\frac{1254}{11} = \frac{12540-1254}{99} = \frac{112.86}{1-0.01} = 112.86 + 1.1286 + \cdots = 114\)

---

Instead of divisibility test, we might as well get the remainder.

1001 = 7×11×13, we can do all factors modulo together.
1000 ≡ -1 (mod 1001), so group digits in sets of 3.

123,456,789 (mod 1001) ≡ 789 - 456 + 123 ≡ 456

123,456,789 (mod 7 ) ≡ 456 ≡ 36 ≡ 1
123,456,789 (mod 11) ≡ 456 ≡ 16 ≡ 5
123,456,789 (mod 13) ≡ 456 ≡ 66 ≡ 1