C++でN番目の丁寧数（ポライト数）を求める方法

丁寧数（ポライト数）とは

丁寧数（polite number）とは、2つ以上の連続する正の整数の和として表すことができる正の整数のことです。

丁寧数の列は以下のようになります。

3, 5, 6, 7, 9, 10, 11, 12, 13, 14 ...

なお、2の累乗（1, 2, 4, 8, 16 ...）は連続する正の整数の和として表せないため、丁寧数には含まれません。この性質が、後述する公式で対数（底2）が使われる理由になっています。

n番目の丁寧数を求める公式

n番目の丁寧数を求めるには、次の公式を使用します。

n + log₂(n + log₂(n))

C++の標準ライブラリにある log 関数はデフォルトで底が e（自然対数）である点に注意が必要です。底2の対数を求めるには、log の計算結果を log(2) で割ります。

アルゴリズム

n番目の丁寧数を求めるアルゴリズムは非常にシンプルです。

• 求めたい番号 N を用意します。
• 計算を実行する前に、n の値を1だけ増やしておきます。
• 上記の公式に従って、n番目の丁寧数を計算します。

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
double getNthPoliteNumber(double n) {
   n += 1;
   return n + (log((n + (log(n) / log(2.0))))) / log(2.0);
}
int main() {
   double n = 10;
   cout << (int)getNthPoliteNumber(n) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

14

この例では n = 10 を渡しているため、10番目の丁寧数である「14」が出力されます。