Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
(파이 함수라고도 부르는) 오일러의 토션트 함수 φ(n)은 n에 대해 상대적으로 소수인 n보다 작거나 같은 양의 정수를 결정하는 함수이다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작으면서 9에 대해서는 소수이므로 φ(9)=6이다.
1은 모든 양의 정수에 대해 상대적으로 소수이므로, φ(1)=1이다.
흥미롭게도 φ(87109)=79180이며, 87109는 79180의 순열이다.
n이 1보다 크고 107보다 작을때, φ(n)이 n의 순열이며, n/φ(n)이 최소인 n을 구하시오.
--------------------------------------------------------------------------
문제가 그렇게 까다롭게 보이지는 않았는데, 50번 이후 문제 대부분이 그렇듯이 1~1천만까지 있는 숫자 중에서 답을 구해야 되는 덕분에 실행시간이 많이 필요하므로, 통상적인 방법으로 시간을 들여 답을 구하거나, 숨어 있는 수학이론을 찾아 빠른 시간 내에 답을 구해야 한다는 것이 실제 문제였다.
69번 문제를 생각해보면, n/φ(n)가 최대인 경우는 n이 크면서, φ(n)이 작은 경우를 구하기 위해, 소수인 약수가 가장 많은 경우를 구해서 해결했다. 70번 문제는 정반대인 n/φ(n)이 최소인 경우를 묻고 있으므로, n이 작으면서 φ(n)이 큰 경우이며, 이 경우를 충족하려면 2개의 소수가 약수인 경우가 될 것이다 (자신이 소수인 경우는 1 작은 수가 순열이 되지 않아 제외). 2개의 소수가 편차가 작을수록 값이 작아질 것이기 때문에 √10000000(천만, 107)인 3300 전후의 두 숫자가 조건을 만족할 것으로 추정되었는데, 자신이 없어서 천~만 사이의 두 소수를 곱해서 나오는 값(n)의 φ(n)이 n의 순열이 되면서 n/φ(n)이 최소인 값을 구하는 과정을 통해 답을 구할 수 있었다.
처음에는 φ(n)을 구하면 순열을 만들어서 n이 있는지 확인했는데, n과 φ(n)을 리스트로 만들어 정렬해서 두 값이 같은지 비교하는 것이 훨씬 빠르게 순열 여부를 확인할 수 있었다.