[20211005] Luhnアルゴリズム面白い

[linzhengen]

参考

https://ja.wikipedia.org/wiki/Luhn%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

アルゴリズム

Luhnアルゴリズムは、チェックディジットを含む数が正しいかどうかを検証する。チェックディジットは通常、一意な番号に付与され、チェックディジットを含めた全体を認証番号などに使う。この番号は以下のようにして検証できる。

右端のチェックディジットを1番目として、偶数番目の桁を2倍にする。 2倍にしていない桁も含め、各数字の総和を求める（2倍にした桁が2桁になった場合は、それぞれを別々の数字として加える）。 この総和の下1桁が0なら（つまり、10で割り切れる場合）、この番号はLuhnアルゴリズムでは正しく、そうでない場合は正しくない。 例として、49927398716 という番号を検証する場合を考える。

右端から偶数番目の桁をそれぞれ2倍する: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18 それぞれの数字の総和を計算する（括弧で囲まれた数字は上のステップで2倍した桁）: 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70 10で割りきれるか調べる: 70 mod 10 = 0 なので、この番号は正しい。

実装例

def check_number(digits):
    _sum = 0
    alt = False
    for d in reversed(digits):
        assert 0 <= d <= 9
        if alt:
            d *= 2
            if d > 9:
                d -= 9
        _sum += d
        alt = not alt
    return (_sum % 10) == 0