整数とその各桁の合計のGCDが1より大きくなる最も近い整数を求めるC++プログラム

ある数 N が与えられたとします。ここで、正整数 x に対して定義される関数 gcdSum(x) は、「その整数自身」と「その整数の各桁の合計（桁和）」の最大公約数（GCD）を表します。この記事では、gcdSum(x) > 1 を満たす最小の整数 x（n 以上）を求める方法を解説します。

例えば、入力が N = 31 の場合、出力は 33 になります。その理由は次の通りです。

• 31 と (3+1)=4 の GCD は 1
• 32 と (3+2)=5 の GCD は 1
• 33 と (3+3)=6 の GCD は 3 ← 初めて 1 より大きくなる

アルゴリズムの手順

この問題は、n から順に候補を調べていくシンプルな手法で解けます。具体的には、以下の手順に従います。

for initialize i := n, when i <= n + 2, update (increase i by 1), do:
    jml := 0
    x := i
    while x > 0, do:
        jml := jml + x mod 10
        x := x / 10
    if gcd of i and jml is not equal to 1, then:
        return i
return 0

処理の流れを整理すると、次のようになります。

1. n から n+2 までの各整数について、各桁の合計（桁和）を計算する。
2. 元の整数と桁和の GCD を求める。
3. GCD が 1 以外であれば、その整数が答えなので返す。

C++での実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    for (long i = n; i <= n + 2; i++) {
        long jml = 0;
        long x = i;
        while (x > 0) {
            jml += x % 10;
            x /= 10;
        }
        if (__gcd(i, jml) != 1) {
            return i;
        }
    }
    return 0;
}
int main() {
    int N = 31;
    cout << solve(N) << endl;
}

入力

31

出力

33

なぜ n+2 まで調べれば十分なのか

このアルゴリズムでは探索範囲を n から n+2 までの3つに限定していますが、これで必ず答えが見つかることが数学的に保証されています。

ポイントは「整数はその桁和と mod 3 で合同である」という性質です。つまり、ある整数が 3 の倍数なら、その桁和も必ず 3 の倍数になります。連続する3つの整数 n, n+1, n+2 のうち、必ず1つは 3 の倍数であり、その整数については GCD が少なくとも 3 になるため、gcdSum > 1 が成立します。したがって、高々3回のチェックで答えが得られるのです。

計算量

ループは最大3回しか回らず、各反復での桁和計算は O(log n)、GCD 計算も O(log n) で行えるため、全体の計算量は O(log n) ときわめて効率的です。大きな n が与えられても高速に動作します。