무리수인 제곱근들의 자릿수 더하기
이 문제를 푸는 데 Math.sqrt를 사용할 수는 없다. Math.sqrt가 리턴하는 double 형의 유효자리 숫자는 고작 17자리에 불과하다. 제곱근의 자릿수를 원하는 만큼 구할 수 있는 다른 방법이 필요하다. 다행히 Sqrt root by substraction에 정수의 제곱근을 구하는 방법이 자세히 나와 있다.
정수 의 제곱근을 구하는 방법은 다음과 같다.
- , 로 놓는다.
- 다음을 반복한다. (R1) 면 (R2) 면 에 을 곱하고, 의 마지막 자리 바로 앞에 을 추가한다.
따라서 제곱근의 처음 자리를 구하는 함수는 다음과 같이 작성할 수 있다.
(defn sqrt
"Compute the first 100 digits of sqrt(n)."
[n]
(loop [a (* 5 n) b 5]
(if (<= (Math/log10 b) (inc 100)) ; b가 101자리까지 계산해야 100자리까지 값이 정확함
(if (>= a b)
(recur (-' a b) (+' b 10))
(recur (*' 100 a) (+' (*' (quot b 10) 100) (rem b 10))))
(quot b 10)))) ; 101째 자리 제거
이제 부터 까지의 자연수 중 제곱근이 무리수인 경우에 대해 sqrt 함수로 제곱근의 처음 자리를 구한 다음 모두 더하면 된다.
(defn solve []
(->> (range 1 (inc 100))
(remove perfect-square?)
(map sqrt)
(map digits)
(flatten)
(apply +)))
실행 결과는 다음과 같다. 빠르게 답을 구한다.
p080=> (time (solve)) "Elapsed time: 92.033557 msecs" 4??86