[C언어 반복문] 약수의 합이 자신의 5배를 넘을 수 있을까?

 

고등학교 시절에 저는 문득 이런 생각을 가지게 되었습니다. 과연 어떤 수의 약수의 합이 자신의 5배를 넘을 수 있을까? 그래서 실제로 그런 수가 존재하는지 C언어의 반복문을 통해 통해 확인해보고자 하였습니다.

 

사실 결론부터 말하자면, 위 사진을 참고해보셔도 그렇겠지만, 이미 구했습니다!

따라서 해법과 탐색 과정을 소개해드리도록 하겠습니다.

---

이론적 배경

우선 어떤 수의 약수의 합이 어떤 수와 비교하였을 때 그 대소 관계에 따라 분류되는 명칭이 다릅니다. 모든 자연수들은 약수의 합과 자신의 대소 관계에 따라 다음의 3가지로 분류될 수 있습니다.

 

어떤 자연수 n에 대하여, n을 제외한 모든 n의 약수들의 합이 n보다 작다면, n을 부족수라고 합니다.

예를 들어, 9의 진약수는 1과 3이 있는데 (진약수이므로 9를 제외하고 고려해야 함) 1+3 < 9이므로 9는 부족수입니다.

 

어떤 자연수 n에 대하여, n을 제외한 모든 n의 약수들의 합이 n과 같다면, n을 완전수라고 합니다.

예를 들어, 6의 진약수는 1, 2, 3이 있는데 1+2+3=6이므로 6은 완전수입니다.

 

어떤 자연수 n에 대하여, n을 제외한 모든 n의 약수들의 합이 n보다 크다면, n을 과잉수라고 합니다.

예를 들어, 12의 진약수는 1, 2, 3, 4, 6이 있는데 1+2+3+4+6=16 > 12이므로 12는 과잉수입니다.

 

우리는 이 세 가지 중에서 과잉수에 대한 의문을 해결해 볼 것입니다. 위에서 예시로 든 과잉수 12의 진약수들의 합은 16으로, 12보다 약 1.33배 큽니다. 그럼 진약수들의 합이 원래 수보다 5배 큰 수는 존재할까요?

 

풀이

우선 우리는 반복문을 이용해 어떤 한 개의 자연수에 대해 그 수의 약수의 합을 구할 수 있습니다.

#include <stdio.h>

int main()
{
    int i, sum = 0;

    scanf("%d", &i);
    for(int j=1; j<i; j++) {
        if(i % j == 0) {
            printf("%d ", j);
            sum += j;
        }
    }
    printf("약수의 총합 : %d, 원래 수에 비해 %.2f배의 크기를 가짐", sum, (float)sum/(float)i);
}

 

위 코드는 간단히 작성해본 코드입니다.

 

어떤 자연수 i를 입력 받으면, j=1부터 i 미만까지 검사하여 모두 약수인지 확인해본 뒤, 약수일 경우 약수의 합 sum에 더해주고 마지막에 총합과 원래 자연수 i의 몇 배 크기를 가지는지 출력해줍니다. 간단히 테스트해보면 다음과 같습니다.

 

잘 출력되는 것을 확인해볼 수 있습니다.

 

그럼 이제, 모든 수에 대해 검사해봅시다. 이중 for문을 만들어 바깥쪽 loop를 i에 대한 반복문으로 만들어주면, 우리는 모든 자연수 각각에 대해 약수의 합을 계산해볼 수 있습니다.

 

#include <stdio.h>

int main()
{
    int i, sum;

    for(i=2; ; i++) {
        sum = 0;
        for(int j=1; j<i; j++) {
            if(i % j == 0) {
                sum += j;
            }
        }
        printf("%d : 약수의 총합 %d, 원래 수에 비해 %.2f배의 크기를 가짐\n", i, sum, (float)sum/(float)i);
    }
}

 

위 코드는 앞서 언급한대로 i=2부터 i를 1씩 늘려주며 모든 i에 대해 약수의 합을 구하고, 그것이 원래 수의 몇 배인지를 출력해주는 코드입니다. 확인해보면 다음과 같습니다.

 

 

프로그램을 시작하자마자 엄청난 속도로 출력이 시작되는데요, 이래서는 우리가 구하는 수를 쉽게 찾을 수 없습니다. 그래서 조건문을 하나 추가하여, 약수의 합이 원래 수의 3배를 넘는 수가 있는지 찾아보도록 하겠습니다.

 

if((float)sum/(float)i > 3.0)

 

출력문 앞에 위와 같은 조건을 추가하였습니다. 이제 실행해볼까요?

 

 

꽤 많은 수들이 출력되긴 합니다만, 굉장히 답답한 속도입니다. 대략 2~3초에 한 개씩 나타나는 것을 확인할 수 있습니다. 조금 더 빨리 찾기위해, 다음과 같은 방법을 사용하고자 합니다.

 

n의 진약수들의 합이 n이라면, 2n의 진약수들의 합은 앞서 말한 n보다 작은 약수들의 합인 n에다가 n 또한 2n의 약수이므로 최소 2n 이상이 될 것입니다. 예를 들어, 6의 진약수들의 합은 1+2+3 = 6이고, 12의 진약수들의 합은 1+2+3=6에다가 6 또한 12의 약수이므로 1+2+3+6만 해도 우선 12 이상임을 알 수 있습니다. 실제로는 4 또한 12의 약수이기 때문에 6의 배수인 12 또한 상당히 큰 약수들의 합을 가짐을 알 수 있습니다.

 

따라서 이 원리를 이용하여 i++ 대신, 위에서 발견한 27720을 기본 증가량으로 설정하고, 진약수들의 합이 원래 수의 3.7배를 넘는 수들만 탐색해보겠습니다. (일종의 야매 풀이입니다만 궁금증에 대한 빠른 해답을 얻고자 이런 방법을 사용하였습니다.)

 

여전히 많은 수들이 나오는 것을 확인할 수 있습니다. 그럼 위의 방법을 다시 사용하여 7207200을 i의 기본 증가량으로 설정하여 다시 돌려보겠습니다.

 

드디어 진약수들의 합이 4배가 넘는 수가 나왔네요. 그럼 저 122522400을 사용하여 다시 찾아보겠습니다.

 

계산 알고리즘 변경

 

여기서부터는 탐색 범위가 int형의 최대 범위인 2147483647을 넘어가기 때문에 모든 정수형을 int에서 long long int형으로 바꿔주어야 합니다. 그리고 수가 굉장히 커지기 때문에 계산 속도가 굉장히 느려짐을 느꼈습니다. 따라서 알고리즘을 다음과 같이 수정하였습니다.

 

#include <stdio.h>

int main()
{
    long long int i, j, sum;

    for(i=367567200; ; i+=367567200) {
        sum = 0;
        for(j=1; j*j<i; j++) {
            if(i % j == 0) {
                sum += j;
                sum += i/j;
            }
        }
        if(j*j == i) sum += j;
        sum -= i;
        if((float)sum/(float)i > 4.1) printf("%lld : 약수의 총합 %lld, 원래 수에 비해 %.2f배의 크기를 가짐\n", i, sum, (float)sum/(float)i);
    }
}

 

보이시나요? 약수를 j = 1부터 i까지 계산하지 않고, j*j < i까지만 계산한 뒤 나머지 하나의 약수는 i/j로 구해주는 방식입니다. 이렇게 하면 원래는 i = n^2 만큼 걸리던 계산 시간을 n으로 줄일 수 있기 때문에 엄청나게 빨라집니다.

 

그리고 진약수의 합을 구하는 과정이기 때문에 마지막에 i를 sum에서 빼주었습니다.

 

 

원래는 4.1배를 넘는 수 한 개 찾는데에도 5초씩 걸리던 프로그램이 4.5배를 넘는 수도 거뜬히 찾아내기 시작했습니다. 이제 41902660800을 증가량 단위로 설정하고, 다시 구해보도록 하겠습니다.

 

결과

 

보이시나요? 드디어 찾았습니다! 대략 20분 정도 탐색한 것 같은데 드디어 나오네요.

이로써 자신을 제외한 모든 약수의 합이 자신보다 5배 이상 큰 수는 존재함을 확인할 수 있습니다.

 

제가 찾은 수는 195643523275200이고, 진약수의 합은 986771447323200으로 원래 수에 비해 5.04배의 크기를 가집니다.

 

이 방법을 무수히 많이 적용한다면, 몇 배든 큰 수를 찾을 수 있을 것 같습니다만, 저로서는 계산 속도의 한계와 수학적 능력의 부족으로 그 무한성을 증명할 방법이 떠오르지 않네요. 애초에 소인수분해 같은 분야들은 암호학에서 쓰이고 있는 것으로 알고, 아주 간단한 해보이는 골드바흐의 추측도 아직까지 증명이 되지 않았으니까요. 그만큼 약수, 소인수분해 분야는 굉장히 흥미로운 분야인 것 같습니다.

 

---

 

어쨌든, 오늘은 약수의 총합이 원래 수보다 6배 큰, 진약수의 합은 원래 수보다 5배 큰 수가 존재함을 C언어 반복문을 통해 확인해보았습니다. C언어는 연산 속도가 빠르기 때문에 이런 노가다 탐색문제에 굉장히 적합한 것 같습니다.

 

앞으로도 이런 흥미로운 주제가 떠오르면 C언어를 통해 답을 얻어보는 시간을 가져보도록 하겠습니다.