ラッキーナンバー（幸運数）とは？再帰アルゴリズムとC++実装で解説

ラッキーナンバー（幸運数）とは

ラッキーナンバーとは、特別な性質を持つ整数のことです。1から始まる自然数列に対して、数値そのものの大小ではなく位置（順番）に基づいて特定の数を取り除いていき、最後まで消されずに残った数がラッキーナンバーとなります。

削除は次のルールに従って行われます。まず2番目ごとの数をすべて削除し、続いて3番目ごとの数を削除します。以降も同様に、段階的に間隔を広げながら削除を繰り返していきます。

具体例：1〜25の場合

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 （1〜25のすべて）
1 3 5 7 9 11 13 15 17 19 21 23 25 （2番目ごとの数を削除）
1 3 7 9 13 15 19 21 25 （3番目ごとの数を削除・開始位置は5）
1 3 7 9 13 15 21 25 （7番目ごとの数を削除・開始位置は19）

この手順を繰り返して最後まで残った 1, 3, 7, 9, 13, 15, 21, 25 … などの数が、ラッキーナンバーと呼ばれます。

入力と出力

入力：ラッキーナンバーかどうかを判定したい数を指定します。ここでは例として 13 を入力します。
出力：13 はラッキーナンバーです。

アルゴリズム

isLuckyNumber(number)

入力 − 判定対象となる数。

出力 − その数がラッキーナンバーであるかどうかの判定結果。

Begin
    counter := 2 （静的な値であり、再帰呼び出しのたびには初期化しない）
    if counter > n, then
        return 1
    if n mod counter = 0, then
        return 0
    n := n - (n / counter)
    counter := counter + 1
    isLuckyNumber(n)
End

このアルゴリズムでは、実際に数列のリストを操作する代わりに、再帰を利用して各段階の削除後における対象の数の「新しい位置」を追跡します。n を n - (n / counter) に更新することで、「counter 番目ごとの数を削除した後の位置」が計算できます。処理の途中で n が counter の倍数になった場合、その数はいずれかの段階で必ず削除されるため、ラッキーナンバーではないと判定されます。

C++による実装例

#include <iostream>
using namespace std;

int counter = 2;     // 再帰処理の中で使用する静的カウンタ

bool isLuckyNumber(int n) {
    if(counter > n)
        return 1;
    if(n%counter == 0)
        return 0;

    n -= n/counter;     // 次の再帰呼び出し用に位置を更新
    counter++;
    return isLuckyNumber(n);
}

int main() {
    int x = 13;

    if(isLuckyNumber(x))
        cout << x<<" is a lucky number.";
    else
        cout << x<<" is not a lucky number.";
}

実行結果

13 is a lucky number.

13 はどの段階でも削除されることなく最後まで残るため、ラッキーナンバーであると判定されます。