C++로 N번째 폴라이트 수(Polite Number) 구하는 방법

폴라이트 수란?

폴라이트 수(polite number)는 2개 이상의 연속된 양의 정수의 합으로 표현할 수 있는 양수를 말합니다. 예를 들어, 5 = 2 + 3처럼 연속된 자연수의 덧셈으로 나타낼 수 있습니다.

폴라이트 수열은 다음과 같습니다.

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

참고로 2의 거듭제곱(1, 2, 4, 8, ...)은 연속된 정수의 합으로 표현할 수 없기 때문에 폴라이트 수에 포함되지 않습니다.

N번째 폴라이트 수를 구하는 공식

N번째 폴라이트 수는 아래 공식을 통해 바로 계산할 수 있습니다.

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

C++의 기본 log 함수는 밑이 e인 자연로그를 계산합니다. 따라서 밑이 2인 로그 값을 구하려면 자연로그 결과를 log(2)로 나누어 변환해 주어야 합니다.

알고리즘

N번째 폴라이트 수를 구하는 알고리즘은 매우 간단합니다.
숫자 N을 초기화합니다.
위 공식을 이용하여 N번째 폴라이트 수를 계산합니다.
계산하기 전에 반드시 n 값을 1만큼 증가시켜야 합니다.

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;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.