자리 숫자이면서 제곱수도 되는 양의 정수는 모두 몇 개?
어떤 수가 제곱수라면 으로 표현할 수 있다. 어떤 수가 제곱수인 동시에 자리 숫자가 되려면 다음 부등식을 만족해야 한다.
위 부등식에서 임을 알 수 있다. 는 정수여야 하므로 에 들어갈 수 있는 값은 다. 의 범위는 다음과 같이 구할 수 있다.
부등식의 양변에 상용로그를 취해 정리하면 다음과 같은 결과를 얻는다.
우변을 계산해보면 가 나오므로, 위 조건을 만족하는 정수 의 최대값은 임을 알 수 있다. 이제 두 변수 과 의 범위를 알았으므로, 자리 수이면서 제곱수가 되는 정수의 개수를 구할 수 있다.
먼저 자리수 이 정해졌을 때 자리 수이면서 제곱수도 되는 수를 찾는 함수를 작성해보자. 처음 부등식에서 왼쪽 부등식을 정리하면 다음과 같은 조건을 찾을 수 있다.
이 부등식을 이용해 자리 수이면서 제곱수도 되는 수를 찾는 함수를 다음과 같이 정의할 수 있다.
(defn power [x n] (apply *' (repeat n x)))
(defn digits&power [n]
(for [x (range 1 10)
:when (<= (/ (dec n) n) (Math/log10 x))]
(power x n)))
이 함수를 이용해 다음과 같이 자리 수이면서 제곱수도 되는 정수의 개수를 구할 수 있다.
(def limit (/ 1 (- 1 (Math/log10 9))))
(defn solve []
(->> (range 1 limit)
(mapcat digits&power)
count))
실행 결과는 다음과 같다.
p063=> (time (solve)) "Elapsed time: 1.769826 msecs" 49