Dãy Aliquot (Aliquot Sequence) trong C++

Dãy Aliquot: bắt đầu từ n, số tiếp theo là tổng các ước số thực sự (proper divisors) của số trước. Dừng khi gặp 0 hoặc lặp lại.

Ví dụ: 8 -> ước thực sự: 1,2,4 -> tổng 7. 7 -> ước: 1 -> tổng 1. 1 -> ước: không có -> tổng 0. Dãy: 8 7 1 0.

Phân loại: Perfect (chu kỳ 1), Amicable (chu kỳ 2), Sociable (chu kỳ >2).

Thuật toán

Bước 1: Hàm SumFactorial(n) tính tổng ước thực sự (dùng sqrt(n) tối ưu).
Bước 2: In n, insert vào set.
Bước 3: Lặp: n = SumFactorial(n); nếu n trong set -> lặp, break; in n; insert set.
Bước 4: Kết thúc khi n=0.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int sumProperDivisors(int n) {
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            if (n / i == i) sum += i;
            else sum += i + n / i;
        }
    }
    return sum - n; // trừ chính n
}

void AliquotSequence(int n) {
    cout << n << " ";
    unordered_set<int> s;
    s.insert(n);
    while (n > 0) {
        n = sumProperDivisors(n);
        if (s.find(n) != s.end()) {
            cout << "\nLap lai tai " << n;
            break;
        }
        cout << n << " ";
        s.insert(n);
    }
}

int main() {
    AliquotSequence(45);
    return 0;
}

Kết quả

45 33 15 9 4 3 1 0