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밖에 없는 소수는 더 이상 계산하지 않도록 하는 등 속도를 빠르게 조정했지만, 수 시간 걸릴 것으로 예상되는 등 속도가 문제가 되는 상황이었다.
하지만, 검증을 위해 나온 중간결과값이 정답이 되어 버려서 느린 성능에도 불구하고 정답을 맞힐 수는 있었다. 다른 사람의 방법을 확인하니 역시나 소인수분해를 응용해서 해결하는 것이 정석인 것 같다.