Pythonで「異なる数のn乗の和」として表せる組み合わせの数を求めるプログラム

問題の概要

ある数 x ともうひとつの数 n が与えられます。このとき、「互いに異なる（一意な）数の n 乗の和」として x を表す方法が何通りあるかを求めるのがこの問題です。

たとえば x = 100、n = 2 の場合、出力は 3 になります。これは以下の 3 通りの表現が可能だからです。

• 6² + 8²
• 10²
• 1² + 3² + 4² + 5² + 7²

アルゴリズムの考え方

この問題は再帰呼び出しを用いて解くのが自然です。手順は以下のとおりです。

• 答えを保持する変数 ans を 0 で初期化します。
• 4つの引数 x、n、cn（現在検討中の数）、cs（それまでの累積和）を受け取るメソッド solve() を定義します。cs の初期値は 0、cn の初期値は 1 です。
• p := cnn を計算します。
• p + cs < x である間、以下を繰り返します。
  • ans := ans + solve(x, n, cn + 1, p + cs)
  • cn := cn + 1
  • p := cnn
• p + cs がちょうど x と一致したら、ans := ans + 1 とします。
• 最後に ans を返します。

このアルゴリズムでは、各候補の数について「その数を採用して和に加える」か「スキップして次の候補へ進む」かを再帰的に探索していきます。これにより、同じ数を二度使わないという条件を満たしたまま、すべての組み合わせを漏れなく調べることができます。

Pythonでの実装例

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

from math import pow

def solve(x, n, cn=1, cs=0):
    ans = 0
    p = pow(cn, n)
    while p + cs < x:
        ans += solve(x, n, cn + 1, p + cs)
        cn = cn + 1
        p = pow(cn, n)

    if p + cs == x:
        ans = ans + 1
    return ans

x = 100
n = 2
print(solve(x, n))

入力

100, 2

出力

3

補足：より安全なべき乗の計算方法

math.pow() は結果を浮動小数点数（float）として返すため、非常に大きな数を扱う場合には誤差が発生する可能性があります。Pythonでは組み込み演算子 ** を使うことで、任意精度の整数のままべき乗を計算できます。

# math.pow の代わりに ** 演算子を使用
p = cn ** n

このように書き換えることで、大きな x や n を扱うケースでも正確な結果を得られます。