아라비아의 한 상인은 세상을 떠나기 전에 세 아들에게 다음과 같은 유언을 남겼다.
"너희에게 낙타 17마리를 남기니, 첫째는 \( \frac{1}{2} \), 둘째는 \( \frac{1}{3} \), 셋째는 \( \frac{1}{9} \)을 산 채로 나누어 가져라."
삼 형제는 아버지의 유언대로 낙타를 나눠 가질 수 없어, 마을의 현자를 찾아갔다.
현자는 삼 형제에게 자신의 낙타 한 마리를 빌려줄테니 아버지의 유언대로 나눠 갖고 나서 다시 돌려 달라했다.
삼 형제는 18마리가 된 낙타를 아버지의 유언대로 첫째는 9마리, 둘째는 6마리, 셋째는 2마리로 나눠 갖고, 현자에게 빌린 한 마리를 다시 돌려주었다.

신기한 이야기다. 처음에는 분명 불가능한 유산 분배였는데, 빌려온 한 마리 덕분에 유산 분배가 되었고 남은 한 마리가 있어 다시 갚았다. 결국, 빌린 낙타 한 마리는 실물로는 없어도 되는 셈이다. 어떻게 이런 일이 가능할까? 이러한 낙타 수와 유산 분배의 비를 일반화할 수 없을까?

일반화된 낙타 수

우선 이야기 속에서 일반화 할 수 있는 수가 무엇인지 모두 찾아보자.

  • 아들의 수 3.
  • 유산 분배의 비 \( \frac{1}{2} \), \( \frac{1}{3} \), \( \frac{1}{9} \).
  • 현자가 빌려주는 낙타의 수 1.

우선 아들의 수와 현자가 빌려주는 낙타의 수를 고정하고, 유산 분배비를 \( \frac{1}{a} \), \( \frac{1}{b} \), \( \frac{1}{c} \)라 하자. a, b, c의 최소공배수를 m이라 할 때, 이야기처럼 유산 분배 문제가 해결되기 위해서는 다음을 만족해야 한다.
\[ \frac{m}{a} + \frac{m}{b} + \frac{m}{c} = m - 1 \]
식을 간단히 하기 위해 우변의 -1을 좌변으로 이항하고, 양변을 m으로 나누면 다음과 같다.
\[ \frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{m} = 1 \]
따라서, 가능한 다른 유산 분배비는 모두 위와 같은 조건을 만족한다.

그런데 위 조건을 만족하는 a, b, c를 찾기는 쉽지 않다. 우선, a, b, c와 같이 여러 수가 모두 독립적이다. 다시 말해, 독립변수가 많다. 그리고 세 수의 최소공배수를 구해야하는데 대체로 최소공배수는 그 값이 급격히 커진다. 따라서, 다른 방향으로 생각할 필요가 있는데, 배수와 가까운 개념인 약수의 관점에서 식을 바꿔볼 수 있다.

위에 있는 마지막 방정식의 양변에 m을 곱하면 다음과 같다.
\[ \frac{m}{a} + \frac{m}{b} + \frac{m}{c} + 1 = m \]
이때, 좌변의 모든 항은 우변 m의 진약수[각주:1]이다. 이 식에서 최소공배수 m을 독립변수로 바라보면, 어떤 수 m이 자신의 진약수 중에서 1을 포함한 일부분의 합으로 표현되었다고 해석할 수 있다.
직접적으로 \( d_{1} = \frac{m}{a} \), \( d_{2} = \frac{m}{b} \), \( d_{3} = \frac{m}{c} \)라고 두고, 좌우변을 바꾸면 다음과 같이 표현된다.
\[ m = 1 + d_{1} + d_{2} + d_{3} \]
이제 m을 n이라 하고, 아들의 수를 3에서 s로 일반화하면 다음과 같이 표현할 수 있다.
\[ n = 1 + d_{1} + \cdots + d_{s} \]

그러므로 일반화된 낙타 수는 1을 포함하는 자기 자신의 어떤 일부 진약수의 합으로 표현되는 수 n에 대하여 n에서 1을 뺀 수 'n-1'로 정의된다.[각주:2]

한편, 일부 진약수의 합이 자기 자신이 되는 수를 반완전수(Semiperfect number)라 한다.[각주:3] 다시 말해, 일반화된 낙타 수는 1을 포함하는 일부 진약수의 합으로 표현되는 반완전수 n에 대한 n-1이다.

이제 실제 일반화된 낙타 수 n-1을 찾기 위해 반완전수 n을 찾아보자. 자연수 중에서 우선 반완전수를 찾아야 한다. 따라서, 자연수 n이 반완전수인지 판별하고 반완전수라면 어떤 진약수의 합으로 표현되는지 알아야 한다.

반완전수 판별 및 분해[각주:4] with AlgeoMath

원본 열기

설명

아래의 알고리즘에 따라 반완전수를 판별하고 반완전수라면 어떤 진약수의 합으로 표현되는지 알 수 있다.

반완전수 판별 알고리즘

  1. 자연수 n을 입력한다.
  2. n을 소인수분해한다.
  3. n의 모든 약수를 구한다.
  4. 약수를 오름차순 또는 내림차순으로 정렬한다.[각주:5]
  5. 모든 진약수의 합을 구한다.
  6. 모든 진약수의 합이 n보다 작으면 부족수(Deficient number)로 판별하고, n이면 완전수로 판별하고, n보다 크면 과잉수(Abundant number)로 판별한다.
    1. 부족수가 되면 진약수로 n을 만들 수 없으므로 끝난다.
    2. 완전수가 되면 모든 진약수의 합 그 자체가 유일한 표현이라 끝난다.
    3. 과잉수이면 일부 약수의 합으로 n을 만들 수 있는지 확인한다.
      1. 만들 수 없으면 n을 기묘수(Weird number)로 판별하고 끝난다.
      2. 만들 수 있으면 n을 반완전수로 판별하고 분해 알고리즘으로 넘어간다.

반완전수 분해 알고리즘

앞서 반완전수로 판별된 n의 모든 진약수 중에서 합으로 n을 만들 수 있는 조합을 찾으면 된다. 이때, 각 진약수는 조합에 포함되거나 안되거나 둘 중의 하나이므로 모든 진약수에서 선택되는 조합은 이진수에 대응된다.
예를 들어, 18의 모든 진약수는 9, 6, 3, 2, 1이다. 이 중에서 9, 6, 2, 1로 선택된 조합은 이진수 11011로 볼 수 있다.
그러므로 모든 진약수의 모든 조합을 이진수의 크기 순서대로 탐색할 수 있다.

한편, 모든 진약수의 합이 n보다 크더라도 특정 진약수 밑으로는 합이 n보다 작을 수 있다. 즉, 특정 진약수 보다 작은 진약수들만으로는 조합을 고려하지 않아도 된다.
예를 들어, 18에서 6, 3, 2, 1만 더하면 12밖에 되지 않으므로 최소한 9를 포함하는 조합부터 고려해야한다. 그리고 최소한 9가 필요하다고 하면, 9를 빼고 다시 최소한 어떤 진약수가 필요한지 고려할 수 있다.
이런 식으로 조합에 꼭 포함해야하는 최소한의 진약수들을 차례대로 결정할 수 있다. 예를 들어, 18에서는 9, 6, 2, 1이 차례대로 결정되므로 이진수 11011부터 탐색하면 된다.

끝나지 않은 문제

알고리즘의 마지막 단계를 마치는 데에 얼마나 걸릴지 예측할 수가 없다.
예를 들어, 진약수의 개수가 17개인 자연수 180은 751가지로 합이 자기 자신이 되는 진약수 조합을 갖지만, 17개로 같은 진약수의 개수를 갖는 1,575는 11가지 진약수 조합을 가진다. 또한, 180의 절반인 90은 23가지 진약수 조합을 갖지만, 180의 두 배인 360은 무려 22,208가지 진약수 조합을 가진다.

이와 같은 문제를 컴퓨터과학에서는 부분집합의 합 문제(Subset sum problem)라고 부른다.[각주:6] 그리고 이런 종류의 문제를 NP-완전 문제로 분류한다.

참고

  1. 자기 자신 보다 작은 약수 [본문으로]
  2. 만약 여기서 현자가 빌려주는 낙타의 수 또한 1에서 k로 일반화하면 일반화된 낙타 수는 k를 포함하는 자기 자신의 어떤 일부 진약수의 합으로 표현되는 수 n에 대하여 n에서 k를 뺀 수 'n-k'가 된다. 그런데 그렇게 일반화하면 1은 항상 진약수이지만, k는 n의 약수가 되어야 하는 조건이 필요하므로 부수적인 조건이 추가된다. 따라서, 현자가 빌려주는 낙타의 수는 1로 정한다. [본문으로]
  3. 모든 진약수의 합이 자기 자신이 되는 수를 완전수(Perfect number)라고 한다. [본문으로]
  4. 반완전수를 어떤 진약수의 합으로 표현하는 것을 분해한다고 볼 수 있으므로 분해라는 이름을 붙였다. [본문으로]
  5. 반완전수를 판별하는 데에는 필요없는 단계이지만, 반완전수일 때 어떤 진약수의 합으로 표현되는지 알기 위해 필요하다. [본문으로]
  6. 마지막 단계는 어떤 자연수의 진약수 집합에서 그 합이 원래 자연수가 되는 부분집합을 찾는 것이다. [본문으로]

티스토리툴바