【C++】アリコット数列の求め方と実装例をわかりやすく解説

アリコット数列とは

アリコット数列(Aliquot Sequence)は、特殊な性質をもった数列です。数列はある整数から始まり、次の項は直前の項の真の約数(その数自身を除く約数)の総和として定義されます。

具体的な例で確認してみましょう。

入力 : 8
出力 : 8 7 1 0
解説 :
    8 の真の約数は 4, 2, 1。その和は 7
    7 の真の約数は 1。その和は 1
    1 の真の約数は存在しないため、その和は 0

完全数・友愛数・社交数との関係

アリコット数列は、以下の3種類の特別な数と深い関わりがあります。

• 完全数:数列の長さが1(自分自身に戻る)となる数。例:6(1 + 2 + 3 = 6)
• 友愛数:数列の長さが2となり、互いに相手へ戻るペア。例:220 と 284(220 の約数の和は 284、284 の約数の和は 220)
• 社交数:数列が長さ3以上のサイクルを形成する数。例:12496 → 14288 → 15472 → 14536 → 14264 → 12496

アリコット数列を求めるには、各項ごとに真の約数を計算する必要があります。ここでは、√n まで試し割りを行うことで効率よく約数を求める手法を採用します。

アルゴリズム

1. 数を初期化します。
2. その数のすべての真の約数を求めます。
3. 真の約数の総和を計算します。
4. 総和を出力し、その値を新しい数として手順1に戻ります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int Sumfactorial(int n){
    int sum = 0;
    for (int i=1; i<=sqrt(n); i++){
        if (n%i==0){
            if (n/i == i)
                sum = sum + i;
            else{
                sum = sum + i;
                sum = sum + (n / i);
            }
        }
    }
    return sum - n;
}
void Aliquotsequence(int n){
    printf("%d ", n);
    unordered_set<int> s;
    s.insert(n);
    int next = 0;
    while (n > 0){
        n = Sumfactorial(n);
        if (s.find(n) != s.end()){
            cout << "\nRepeats with " << n;
            break;
        }
        cout << n << " ";
        s.insert(n);
    }
}
int main(){
    Aliquotsequence(45);
    return 0;
}

実行結果

45 33 15 9 4 3 1 0

このプログラムでは、unordered_set を使ってすでに出現した値を記録しています。同じ値が再び現れた場合(サイクルが検出された場合)は処理を終了するため、完全数や友愛数のように無限ループに陥る可能性のあるケースでも安全に停止できます。