Pythonで3の倍数と7の倍数の組み合わせで数値nを作れるか判定する方法

ある正の整数 n が与えられたとき、その n を「3の非負の倍数」と「7の非負の倍数」の合計として表すことができるかどうかを判定する問題を考えてみましょう。

例えば、入力が 13 の場合、出力は True になります。なぜなら、13 = 1×7 + 2×3 と表せるからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• i を 0 から n+1 まで、7 ずつ増やしながら繰り返します。
• 各 i について、(n − i) が 3 で割り切れるかどうかを確認します。
• 割り切れる場合は True を返します。

ループを最後まで回っても条件を満たさなかった場合は、False を返します。

このアルゴリズムの考え方はシンプルです。「7の倍数」をいくつ使うかを全通り試し、残りの部分が「3の倍数」だけで埋められるかを調べています。7の倍数を i だけ使うと決めれば、残りの n − i はすべて3の倍数で構成される必要があるためです。

実装例

以下にPythonでの実装例を示します。

class Solution:
    def solve(self, n):
        for i in range(0, n + 1, 7):
            if (n - i) % 3 == 0:
                return True
        return False

ob = Solution()
print(ob.solve(13))

入力

13

出力

True

補足：計算量について

この実装では、i を 7 ずつ増やしながら最大 n/7 回程度ループするため、時間計算量は O(n) となります。より効率的にしたい場合は、数学的な性質を利用できます。

実は、3と7は互いに素なので、十分大きな整数はすべて3の倍数と7の倍数の和で表せることが知られています（このような境界値は「フロベニウス数」と呼ばれ、3と7の場合は 3×7 − 3 − 7 = 11 となります）。つまり、12 以上の整数は必ず True となり、判定が必要なのは小さい数だけです。

また、剰余演算を使えば、n mod 7 の値ごとに必要な3の倍数の個数が決まるため、O(1) で判定することも可能です。