오일러 프로젝트 29

접근

일련의 값에 대해서 가장 빠르게 중복을 제거하는 방법 중 하나는 set()를 사용하는 것이다. 2~100 사이의 수에 대해서 중복 루프를 돌면서 x^y를 집합에 추가한 후 최종적으로 중복이 제거된 집합의 원소 수를 세면 된다.

%%time
a = set(x**y for x in range(2, 101) for y in range(2, 101))
print(len(a))

지수법칙을 활용하기

큰 수를 지원하지 않는 언어를 사용하거나, 혹은 이렇게 큰 수를 사용하는 것이 반칙같다는 느낌이 든다면 조금 두뇌를 더 회전시켜 보자. x^y를 직접 계산하지 않고 밑과 지수로 나누어서 (x, y)로 표현하자. 그리고 이번에는 8⁶을 밑과 지수의 순서쌍으로 표현하는 방법을 생각해보자.

\begin{align}
8^6 &= (2^3)^6 \\
&= 2^{18} 
\end{align}

즉 순서쌍으로 표현한 (8, 6)은 (2³, 6)이므로 지수법칙에 의해 (2, 18)이 되는 것을 알 수 있다. 따라서 밑을 더 작은 수의 거듭제곱으로 교체한다면 이 방식으로 전체 값을 계산하지 않아도 같은 수를 판별할 수 있다. 문제의 조건에서 a, b는 모두 2와 100사이의 수이고, 2⁷ > 100 이므로 a는 더 작은 수 k의 제곱에서 6승 사이의 수와 같은지 확인하면 된다. 또한 더 작은 수 k는 a의 제곱근 이하의 수만 확인하면 될 것 같다.

def transform(a: int, b: int) -> tuple[int, int]:
  for k in range(2, int(a**.5+1.5)):
    for i in range(2, 7):
      if k**i == a:
        return (k, b * k)
      elif k > a:
        break
  return (a, b)

print(transform(8, 6))
# (2, 18)

ns = set(transform(a, b) for a in range(2, 101) for b in range(2, 101))
print(len(ns))