C++で婚約数（Betrothed Number）を求める！アルゴリズムと実装例を解説

婚約数（Betrothed Number）とは？

婚約数とは、2つの整数の組のうち、「一方の数の真の約数（その数自身を含まない約数）の総和が、もう一方の数よりちょうど1大きい」という性質を満たすペアのことです。この記事では、C++を用いて指定した範囲内に存在する婚約数のペアをすべて見つける方法を解説します。

最も有名な例が (48, 75) のペアです。

• 48 の真の約数：{1, 2, 3, 4, 6, 8, 12, 16, 24} → 総和は 76（= 75 + 1）
• 75 の真の約数：{1, 3, 5, 15, 25} → 総和は 49（= 48 + 1）

互いの約数和が相手の数より1だけ大きいため、この2つの数は婚約数の関係にあるといえます。友愛数（Amicable Number）が「約数和が互いに相手の数と一致する」ペアであるのに対し、婚約数はその差がちょうど1である点が特徴です。

アルゴリズム

1からnまでの各整数について真の約数の総和を求め、条件を満たすペアを探索します。約数和の計算では、平方根までの試し割りを行い、約数iが見つかれば対になる約数（num / i）も同時に加算することで、計算量を抑えています。また、約数和が自分自身より大きい場合のみ相手候補（sum − 1）を調べることで、同じペアの重複チェックを防いでいます。

BetrothedPairs(n) −
begin
   for num in range 1 to n, do
      sum := 1
      for i in range 2 to √num, do
         if num is divisible by i, then
            sum := sum + i
            if i * i ≠ num, then
               sum := sum + num / i
            end if
         end if
      done
      if sum > num, then
         num2 := sum − 1
         sum2 := 1
         for j in range 2 to √num2, do
            if num2 is divisible by j, then
               sum2 := sum2 + j
               if j * j ≠ num2, then
                  sum2 := sum2 + num2 / j
               end if
            end if
         done
         if sum2 = num + 1, then
            print the pair (num, num2)
         end if
      end if
   done
end

C++による実装例

#include <iostream>
using namespace std;

// 真の約数の総和を利用して婚約数のペアを探索する
void BetrothedPairs(int n) {
    for (int num = 1; num < n; num++) {
        int sum = 1;
        // 平方根まで調べて真の約数をすべて求める
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) // 同じ約数を二重に加算しない
                    sum += num / i;
            }
        }
        if (sum > num) {
            int num2 = sum - 1;
            int sum2 = 1;
            for (int j = 2; j * j <= num2; j++) {
                if (num2 % j == 0) {
                    sum2 += j;
                    if (j * j != num2)
                        sum2 += num2 / j;
                }
            }
            if (sum2 == num + 1)
                cout << "(" << num << ", " << num2 << ")" << endl;
        }
    }
}

int main() {
    int n = 5000;
    BetrothedPairs(n);
}

実行結果

n = 5000 として実行すると、次の婚約数のペアが出力されます。

(48, 75)
(140, 195)
(1050, 1925)
(1575, 1648)
(2024, 2295)

まとめ

婚約数は、友愛数の変種ともいえる興味深い数論の概念です。約数和を平方根までの試し割りで効率的に求めることで、大きな範囲でも高速にペアを探索できます。ぜひnの値を変更して、より大きな婚約数を探してみてください。