整数を一意の自然数のn乗の合計として表現できる方法を見つけるC++プログラム

この記事では、整数（たとえばX）を一意の自然数のn乗の合計として表現する方法を見つけるプログラムについて説明します。

たとえば、X=100およびn=2

次に、100を自然数の2乗の合計として表す3つの方法があります。

100 = 102
100 = 62 + 82
100 = 12 + 32 + 42 + 52 + 72

これは、再帰を使用することで簡単に実行できます。 1から始めて、指定された数のn乗根まで進みます。すべての実行で、与えられた数から自然数のn乗（1から始まり）を、数が未満になるまで減算します。これにより、自然数のn乗の合計として数を表す方法がわかります。

例

#include<iostream>
#include <math.h>
using namespace std;
int result = 0;
int ways(int number, int a, int init, int n){
   if (a == 0) {
      result++;
   }
   //setting the higher limit
   int max = (int)floor(pow(number, 1.0 / n));
   for (int i = init + 1; i <= max; i++) {
      //subtracting n-th power values starting from 1
      int b = a - (int)pow(i, n);
      if (b >= 0)
         ways(number, a - (int)pow(i, n), i, n);
   }
   return result;
}
int main() {
   int a = 100, n = 2;
   cout << ways(a, a, 0, n);
   return 0;
}

出力

3