φ(n)이 n의 순열이 되는 수 조사하기
이 의 순열이 되는 수 중에서 이 최소가 되는 을 구해야 한다. 이 다음과 같이 표현될 수 있음을 문제 69에서 확인했다.
의 값이 최소가 되려면 분모가 최대가 되어야 한다. 의 소수인 약수 개수가 늘어날수록 분모는 점점 작아진다. 소수인 약수의 개수는 적을 수록 좋고 소수의 값 자체는 클수록 분모가 커진다. 소수인 약수의 개수가 한 개뿐이고 그 값이 에 최대한 가까운 값을 구하면 이 최소가 될 것이다. 그러나 이 경우는 이 되어 이 의 순열이 될 수 없다.
그 다음 생각할 수 있는 것은 소수인 약수가 두 개이고 각 소수가 모두 에 가까운 값을 가지는 경우다. 따라서 이 숫자를 기준으로 적절한 범위, 즉 2000에서 4000 사이의 소수를 탐색해 조건을 만족하는 값을 구한다면 답을 찾을 수 있을 것이다.
소수인 약수가 두 개뿐이라면 은 다음과 같이 간단히 구할 수 있다.
따라서 두 소수를 받아 을 구하는 함수는 다음과 같이 작성할 수 있다.
(defn phi [p1 p2]
(* (dec p1) (dec p2)))
한 수가 다른 수의 순열인지 확인하는 함수는 다음과 같이 작성할 수 있다.
(defn permutation? [m n]
(= (sort (digits m)) (sort (digits n))))
이제 2000에서 4000 사이의 소수에 대해 을 구해 이 의 순열이 되는 경우만 걸러내 이 최소가 되는 을 구하면 된다.
(def ps
(->> primes
(drop-while #(< % 2000))
(take-while #(< % 4000))))
(defn solve []
(->> (for [p1 ps, p2 ps :when (< (* p1 p2) 10000000)]
[p1 p2 (phi p1 p2)])
(filter (fn [[p1 p2 phi]] (permutation? (* p1 p2) phi)))
(map (fn [[p1 p2 phi]] (/ (* p1 p2) phi)))
(apply min)
numerator))
실행 결과는 다음과 같다.
p070=> (time (solve)) "Elapsed time: 110.29622 msecs" 831??23