立方数ペアの探索 – O(n^(2/3)) 解法を C++ で実装

問題概要

ある整数 n が与えられたとき、n を「2つの立方数の和」として表せる 2 組の異なるペアを見つけるのが本記事のテーマです。具体的には、n = a³ + b³ = c³ + d³ を満たすようなペア (a, b) と (c, d) を求めます。

この種の数は「タクシー数（Taxicab Number）」として知られており、最も有名な例は 1729 = 1³ + 12³ = 9³ + 10³（通称：ラマヌジャン数）です。

解法の考え方

重要なポイントは、a、b、c、d のすべてが n^1/3 以下の範囲に収まるという点です。そこで、n^1/3 以下の数から作られるすべての異なるペア (x, y) を順番に調べ、x³ + y³ が与えられた数 n と一致するものを探します。

一致したペアは、その和の値をキーとしてハッシュテーブル（map）に格納します。そして、同じ和が再び見つかった時点で、保存しておいたペアと現在のペアの両方を出力すればよいのです。組み合わせの総数はおよそ O(n^2/3) 個であるため、全体の計算量もこれに比例して抑えられます。

アルゴリズム

getPairs(n):
開始
　　cube_root := n の立方根
　　map（キー: int型、値: pair型）を用意
　　i を 1 から cube_root まで繰り返す
　　　　j を i+1 から cube_root まで繰り返す
　　　　　　sum = i^3 + j^3 を計算
　　　　　　sum が n と等しくなければ、次の反復へスキップ
　　　　　　sum が map に既に存在すれば、保存済みペアと (i, j) を出力
　　　　　　存在しなければ、sum をキーとして (i, j) を map に挿入
　　　　内側のループ終了
　　外側のループ終了
終了

C++ 実装例

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int getPairs(int n){
   int cube_root = pow(n, 1.0/3.0);
   map<int, pair<int, int> > my_map;
   for(int i = 1; i<cube_root; i++){
      for(int j = i + 1; j<= cube_root; j++){
         int sum = i*i*i + j*j*j;
         if(sum != n)
         continue;
         if(my_map.find(sum) != my_map.end()){
            cout << "(" << my_map[sum].first << ", " << my_map[sum].second << ") and (" << i << ", " << j << ")" << endl;
         }else{
            my_map[sum] = make_pair(i, j);
         }
      }
   }
}
int main() {
   int n = 13832;
   getPairs(n);
}

実行結果

(2, 24) and (18, 20)

この出力は、13832 = 2³ + 24³ = 18³ + 20³ という関係が正しく成立していることを示しています。

計算量

• 時間計算量: O(n^2/3) ― 立方根以下の数から選ばれるペアの総数に比例します。
• 空間計算量: O(n^2/3) ― マップに保存されるエントリの数に依存します。