bonotakeの日記

元・ソフトウェア工学系研究者、今・AI系エンジニア

11の倍数の判定法

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

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


(ここから)

任意の非負整数Nを

N=Σ(102n+1an + 102nbn)

で表す。(n, an, bnは非負整数)

102n=100n=99(100n-1+100n-2+...+1)+1
102n+1=10*100n=10*99(100n-1+100n-2+...+1)+10 = 10*99(100n-1+100n-2+...+1)+11-1

なので

N=Σ(10*99(100n-1+100n-2+...+1)an + 11an + 99(100n-1+100n-2+...+1)bn) +Σ(bn-an)
≡Σbi-Σaj (mod 11)

(ここまで)


あと個人的には、ばーっと2組足してあとで引くより、足して引いて足して引いて…とする方が好みなので(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.
注:bonotakeは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。