C++로 우드홀 수(Woodall Number) 판별하기

우드홀 수(Woodall Number)란 무엇인가?

이번 문제에서는 하나의 자연수가 주어졌을 때, 그 수가 우드홀 수(Woodall Number)에 해당하는지 판별하는 것이 목표입니다.

우드홀 수는 수학자 H. J. 우드홀(H. J. Woodall)의 이름에서 유래한 특수한 수열로, 다음과 같은 형태를 가집니다.

W_n = n · 2ⁿ − 1

여기서 n은 양의 정수입니다. 즉, "n과 2의 n제곱을 곱한 값에서 1을 뺀 수"가 바로 n번째 우드홀 수입니다. 처음 다섯 개의 우드홀 수는 1, 7, 23, 63, 159입니다.

입력 및 출력 예시

간단한 예를 통해 문제를 이해해 보겠습니다.

입력:

X = 159

출력:

Yes

실제로 159 = 5 × 2⁵ − 1 = 5 × 32 − 1이므로 우드홀 수임을 확인할 수 있습니다.

문제 해결 접근 방법

주어진 수의 성질을 잘 관찰하면 이 문제를 매우 효율적으로 해결할 수 있습니다.

짝수 판별: 모든 우드홀 수는 n·2ⁿ−1 꼴이므로 항상 홀수입니다. 따라서 입력값이 짝수라면 즉시 우드홀 수가 아니라고 판정할 수 있습니다.
1을 더한 후 2로 반복해서 나누기: 입력값에 1을 더하면 n·2ⁿ 형태가 됩니다. 이 값을 계속 2로 나누면서 나눈 횟수(p)를 카운트하고, 매 단계마다 "나눈 횟수"와 "남은 값"이 같아지는지 확인합니다.
판정: 두 값이 일치하는 시점이 존재하면 그 수는 우드홀 수입니다. n·2ⁿ을 2로 정확히 n번 나누면 n이 남기 때문입니다.

C++ 구현 코드

위 알고리즘을 구현한 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;

bool isWoodallNumber(int x){
    // 우드홀 수는 항상 홀수이므로 짝수는 제외
    if (x % 2 == 0)
        return false;
    // 첫 번째 우드홀 수 처리
    if (x == 1)
        return true;
    // x + 1 = n * 2^n 형태로 변환
    x += 1;
    int p = 0; // 2로 나눈 횟수
    while (x % 2 == 0){
        x = x / 2;
        p++;
        // 나눈 횟수와 남은 값이 같으면 우드홀 수
        if (p == x)
            return true;
    }
    return false;
}

int main() {
    int x = 1424;
    cout << x;
    (isWoodallNumber(x)) ? cout << " is a Woodall Number"
                          : cout << " is not a Woodall Number";
    return 0;
}

실행 결과

1424 is not a Woodall Number

1424는 짝수이므로 우드홀 수가 아님이 즉시 판별됩니다.

마무리

이 알고리즘은 매 반복마다 입력값을 절반으로 줄여 가므로 시간 복잡도가 O(log N)으로 매우 효율적입니다. 참고로 우드홀 수 중 소수인 것을 '우드홀 소수'라고 부르며, 처음 몇 개는 7, 23, 383 등이 있습니다. 이처럼 수학적 성질을 코드로 옮기면 복잡해 보이는 판별 문제도 간결하게 해결할 수 있습니다.