C 언어로 배우는 약혼수(Betrothed Numbers): 개념부터 코드 구현까지

약혼수(Betrothed Numbers)란?

약혼수는 두 수 사이의 특별한 관계를 나타내는 수 쌍으로, 각 수의 진약수 합에 1을 더했을 때 서로 상대방의 값과 일치하는 경우를 말합니다.

수학적으로 표현하면, 두 수 (a, b)가 약혼수 쌍이 되려면 s(a) = b + 1이면서 동시에 s(b) = a + 1을 만족해야 합니다. 여기서 s(n)은 n의 진약수 합(aliquot sum), 즉 자기 자신을 제외한 약수들의 합을 의미합니다. 이 조건은 σ(a) = σ(b) = a + b + 1과 동치이며, σ는 모든 약수의 합을 구하는 함수입니다.

가장 작은 약혼수 쌍들은 다음과 같습니다.
(48, 75), (140, 195), (1050, 1925), (1575, 1648), (2024, 2295), (5775, 6128)

흥미로운 점은 지금까지 발견된 모든 약혼수 쌍이 홀수와 짝수로 이루어져 있다는 사실입니다. 만약 기수성(parity)이 같은 쌍이 존재한다면, 그 값은 10¹⁰을 넘어야 한다고 알려져 있습니다.

판별 알고리즘

1단계: 두 수 각각에 대해 모든 약수의 합을 구한다.
2단계: 한 수의 약수 합에 1을 더한 값이 다른 수와 일치하는지 확인한다.
3단계: 두 조건이 모두 성립하면 약혼수 쌍이며, 그렇지 않으면 약혼수가 아니다.

예시

입력: a = 48, b = 75
출력:
48과 75는 약혼수입니다

동작 원리

먼저 48의 약수를 살펴보면 1, 2, 3, 4, 6, 8, 12, 16, 24이며, 이들의 합은 76입니다.

75의 약수는 1, 3, 5, 15, 25이고, 합은 49입니다.

48의 약수 합(76)은 75 + 1과 같고, 75의 약수 합(49)은 48 + 1과 같습니다. 따라서 두 수는 약혼수 관계임을 알 수 있습니다.

코드로 구현할 때는 for 루프를 사용해 1부터 a - 1까지의 숫자를 하나씩 검사합니다. 루프 내에서 현재 숫자가 a를 나누어 떨어뜨리는지 확인하고, 가능하다면 그 값을 aDivisorSum에 누적합니다. 루프가 종료되면 aDivisorSum에는 a의 모든 약수의 합이 저장됩니다.

같은 방식으로 두 번째 수 b의 약수 합을 구해 bDivisorSum에 저장합니다.

마지막으로, 한 수의 약수 합에 1을 더한 값이 다른 수와 일치하는지 교차 검증합니다. 두 조건이 모두 참이면 두 수는 약혼수이고, 하나라도 만족하지 않으면 약혼수가 아닙니다.

C 코드 예제

#include <stdio.h>

int main() {
    int i;
    int a, b;
    int aDivisorSum = 0;
    int bDivisorSum = 0;

    a = 48;
    b = 75;

    /* 첫 번째 수 a의 약수 합 계산 */
    for(i = 1; i < a; i++) {
        if(a % i == 0) {
            aDivisorSum += i;
        }
    }

    /* 두 번째 수 b의 약수 합 계산 */
    for(i = 1; i < b; i++) {
        if(b % i == 0) {
            bDivisorSum += i;
        }
    }

    /* 약혼수 조건 검사 */
    if((a + 1 == bDivisorSum) && (b + 1 == aDivisorSum)) {
        printf("%d과 %d는 약혼수입니다\n", a, b);
    } else {
        printf("%d과 %d는 약혼수가 아닙니다\n", a, b);
    }
    return 0;
}

실행 결과

48과 75는 약혼수입니다

시간 복잡도 참고

위 코드는 두 수 각각에 대해 선형 탐색을 수행하므로 전체 시간 복잡도는 O(a + b)입니다. 약수를 √n까지만 검사하고 짝을 처리하도록 최적화하면 O(√n)으로 개선할 수 있습니다.