책 이야기

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

숫자의 진약수는 자신을 제외한 약수이다. 예를 들어, 28의 진약수는 1, 2, 4, 7, 14이다. 진약수의 합계가 28이므로, 완벽수라 부른다. 흥미롭게도 220의 진약수의 합은 284이고, 284의 진약수의 합은 220이어서 두 숫자간에 체인을 만든다. 이런 이유로, 220과 284는 친화쌍(우애쌍, 친구쌍, amicable pair)이라 부른다.

더 긴 체인은 잘 알려져 있지 않다. 예를 들어, 12496으로 시작하면 5개 숫자의 체인을 만든다.

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)

이 체인은 시작 지점으로 돌아오기 때문에, 친화 체인(amicable chain)이라 부른다.

요소가 1백만을 넘지 않는 가장 긴 친화 체인의 가장 작은 수를 구하시오.

--------------------------------------------------------------------------

친화쌍(amicable pair) 등 일부 명칭은 한글로 찾을 수 없어서 친화수(amicable number)와 연계해서 친화쌍, 친화 체인으로 임의로 번역을 했다.

파이썬을 이용해 진약수 구하기, 진약수의 합 구하기, 체인 만들기 등은 이제 어렵지 않는 부분인데, 테스트로 몇 개 숫자를 대상으로 실행해보니 몇 가지 추가로 고려해야 할 것이 있었다. 모든 수가 체인을 만든다고 생각을 하고 다른 예외상황을 생각하지 않았는데, 고려할 사항을 예로 들면 소수가 되면 다음 숫자는 1이 되면서 무한 반복하고, 6이 되어도 6을 무한반복하고, 562로 시작하면 중간에 220과 284를 반복하고 있었다.

이렇게 하고도, 1백만까지 반복하려 하니 시간이 너무 많이 걸리는 문제가 있어, 이미 체인으로 파악한 경우에는 다시 진약수를 구하고 체인을 만드는 과정을 반복하지 않도록 하고, 약수가 1밖에 없는 소수는 더 이상 계산하지 않도록 하는 등 속도를 빠르게 조정했지만, 수 시간 걸릴 것으로 예상되는 등 속도가 문제가 되는 상황이었다.

하지만, 검증을 위해 나온 중간결과값이 정답이 되어 버려서 느린 성능에도 불구하고 정답을 맞힐 수는 있었다. 다른 사람의 방법을 확인하니 역시나 소인수분해를 응용해서 해결하는 것이 정석인 것 같다.

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

숫자 체인은 각 자릿수를 더하여 새로운 숫자를 구하는 것을 끝날때까지 반복하면서 생성된다.

예를 들면 다음과 같다.

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

따라서, 어떤 체인이든 1 또는 89가 되면 무한반복되면서 정체된다. 가장 놀라운 것은 모든 숫자는 결국 1 또는 89에 이른다는 것이다.

1천만 이하의 숫자 중에 89가 되는 숫자는 몇 개인가?

--------------------------------------------------------------------------

10자리수 이상은 자릿수별로 쪼개어서 제곱하고 더하는 과정을 반복하면서 89가 나오는 경우의 수를 더하도록 하면 되는 문제이다. 다만, 1천만 까지 계산하기를 요구했기 때문에 시간은 생각보다 엄청 많이 필요하게 된다.

그래도, 이 방법이 가장 정확한 방법이라 생각하고 속도를 조금 개선해보기 위해 제곱수를 매번 계산하지 않고 리스트를 만들어서 참조하게 했다. 그렇게 해서 256초가 245초로 조금 개선될 수 있었다.

문제를 해결한 후에, 인터넷을 검색해보니 동일한 순열(4666777과 6466777, 7664776)에 대해서는 한 번 계산한 결과를 이용하여 모든 체인을 계산하지 않도록 성능 개선이 가능하다고 되어 있다. 정말 세상은 넓고 해결방안은 다양하다는 것을 새삼 느끼게 된다.