알리쿼트 수열(Aliquot Sequence)은 독특한 규칙을 따르는 수열입니다. 수열은 임의의 수에서 시작하며, 다음 항은 바로 앞 항의 진약수(자기 자신을 제외한 양의 약수)들을 모두 더한 값이 됩니다.
개념을 더 잘 이해할 수 있도록 간단한 예시를 살펴보겠습니다.
입력 : 8
출력 : 8 7 1 0
설명 :
8의 진약수는 4, 2, 1이며, 그 합은 7입니다.
7의 진약수는 1이며, 그 합은 1입니다.
1의 진약수는 없으며, 그 합은 0입니다.
따라서 수열은 8 → 7 → 1 → 0으로 끝납니다.
완전수 · 우애수 · 사교수
알리쿼트 수열의 길이와 순환 패턴에 따라 수를 다음과 같이 분류할 수 있습니다.
- 완전수(Perfect Number) – 알리쿼트 수열의 길이가 1인 수, 즉 진약수의 합이 자기 자신과 같은 수입니다. 예를 들어 6은 6 = 1 + 2 + 3이므로 완전수입니다.
- 우애수(Amicable Number, 친화수) – 알리쿼트 수열의 길이가 2인 수입니다. 두 수가 서로 상대방의 진약수 합이 되는 쌍을 의미하며, 대표적인 예로 220과 284가 있습니다.
- 사교수(Sociable Number) – 알리쿼트 수열의 길이가 3 이상인 수입니다. 세 개 이상의 수가 순환 고리를 이루는 경우를 말합니다.
어떤 수로부터 알리쿼트 수열을 계산하려면 각 항의 진약수를 구해야 하는데, 이때 나눗셈 알고리즘(√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;
}
코드 설명
Sumfactorial() 함수는 1부터 √n까지만 검사하면서 약수를 짝(i, n/i) 형태로 찾아 합을 누적한 뒤, 마지막에 n을 빼서 진약수의 합만 반환합니다. 덕분에 O(√n) 시간 복잡도로 빠르게 계산할 수 있습니다.
Aliquotsequence() 함수는 현재 값을 출력한 뒤 진약수의 합을 다음 항으로 삼아 반복합니다. 이때 unordered_set을 사용해 이미 등장했던 값이 다시 나타나는 경우(순환 발생)를 감지하여, 무한 루프에 빠지지 않고 안전하게 종료됩니다.
실행 결과
45 33 15 9 4 3 1 0
45부터 시작한 알리쿼트 수열은 33 → 15 → 9 → 4 → 3 → 1 → 0으로 이어지며, 진약수를 갖지 않는 0에 도달하면 수열이 종결됩니다.