11の倍数の判定法 - bonotakeの日記

その方法では、各ケタを1つずつ飛ばして足す。すると1つの自然数から2つの合計値が出てきます。その合計値が一致するか、差が11の倍数のとき、もとの数も11の倍数なのです。
(略)
なぜそうなるかも本当はそんなに難しくありませんが……。

私ゃハッカーじゃないので手で証明した方がﾊﾔｽ
つか高１のとき、面白がっていろんな数の判定法見つけて遊んでました。

（ここから）

任意の非負整数Nを

N＝Σ(10²ⁿ⁺¹a_n + 10²ⁿb_n)

で表す。（n, a_n, b_nは非負整数)

10²ⁿ＝100ⁿ＝99(100^n-1+100^n-2+...+1)+1
10²ⁿ⁺¹＝10*100ⁿ＝10*99(100^n-1+100^n-2+...+1)+10 ＝ 10*99(100^n-1+100^n-2+...+1)+11-1

なので

N＝Σ(10*99(100^n-1+100^n-2+...+1)a_n + 11a_n + 99(100^n-1+100^n-2+...+1)b_n) +Σ(b_n-a_n)
≡Σb_i-Σa_j (mod 11)

（ここまで）

あと個人的には、ばーっと２組足してあとで引くより、足して引いて足して引いて…とする方が好みなので（11以外の数の判定方法も、適当に係数をかけつつそうやるとできる場合が多いし）、なので計算ちょっといじってみました。以下のコード、jmukさんのに上書きしてます。

import Test.QuickCheck

newtype Rank = R Integer deriving Show
data Op = Add | Sub deriving (Eq, Show)
        
instance Arbitrary Rank where
    arbitrary = fmap (R . (`mod` 10)) arbitrary


f :: [Rank] -> Integer
f l = foldl (+) 0 $ zipWith (\(R x) n -> x * 10 ^ (n-1))  l [1..]

g :: [Rank] -> Integer
g rs = g1 0 rs Add

g1 :: Integer -> [Rank] -> Op -> Integer
g1 n [] _ = n
g1 n (R v:rs) op
    | op == Add = g1 (n+v) rs Sub
    | op == Sub = g1 (n-v) rs Add

c l = (f l `mod` 11 == 0) == (g l `mod` 11 == 0)

quickCheck。

*Main> quickCheck c
OK, passed 100 tests.