오일러 프로젝트 63

n자리 수이면서 n제곱도 되는 양의 정수는 모두 몇 개?

다섯 자리 수인 16807은 7⁵으로 5제곱수입니다. 또, 아홉자리 수인 134217728은 8⁹으로 9제곱수입니다.

n자리 수이면서 n 제곱수도 되는 양의 정수는 모두 몇 개나 있습니까?

https://euler.synap.co.kr/problem=63

접근

자리 수는 상용로그를 통해서 구할 수 있다. 상용로그값의 정수부에 1을 더하면 원래의 수가 몇 자리로 되어 있는지 알 수 있다. 그렇다면 m의 n제곱이 어떤 수 A 일 때, A가 n 자리의 숫자라면, 이 관계식의 양변에 로그를 적용하여 아래와 같은 식으로 전개하여 n의 최대 범위를 구할 수 있다.

이 범위만 유도해낸다면 아주 쉽게 풀리는 문제이다.

참고로 m은 10보다 작은 자연수여야 한다. (두 자리 수를 제곱해서 두 자리 자연수가 될 수 없으므로…)

\begin{array}{llll}
\log_{10}m^n &=& n - 1 + k & ( 0 \le k \lt 1) \\
n \cdot \log_{10}{m} &\le& n - 1 \\
n(\log_{10}{m} - 1) &\le& - 1 \\
n &\le& 1 \div (1 - \log_{10}{m} )
\end{array}

m의 n제곱이 n자리가 될 수 있는 n의 최대 값은 (1 – (1 / log(m)) 으로 판정된다. 이 점을 이용해서 2 ~ 9 범위의 각 a에 대해서 최대 b 범위를 루프를 돌 수 있다. 전체 루프 수는 몇 번 되지 않기 때문에 답은 쉽게 구해진다.

from math import log10

s = set()
for a in range(2, 10):
  upper = int(1 / (1 - log10(a))) + 1
  for b in range(upper):
    s.add(a**b)
print(len(s))

# 48