프로젝트 오일러 69

69번 풀이를 빼먹고 70번을 넘어갔었다. 69번 문제는 오일러 피 함수에 관한 문제인데, 문제를 주의깊게 읽어보면 사실 피 함수를 작성하는 것이 목적이 아니다.

오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(9)=6이 됩니다.

위에서 보듯이 n ≤ 10인 경우 n/φ(n)의 값은 n=6일때 최대가 됩니다.

n이 1,000,000 이하의 자연수일 때, n/φ(n)는 언제 최대가 됩니까?

n	서로 소인 수	φ(n)	n/φ(n)
2	1	1	2
3	1, 2	2	1.5
4	1, 3	2	2
5	1, 2, 3, 4	4	1.25
6	1, 5	2	3
7	1, 2, 3, 4, 5, 6	6	1.1666…
8	1, 3, 5, 7	4	2
9	1, 2, 4, 5, 7, 8	6	1.5
10	1, 3, 7, 9	4	2.5

오일러 피함수는 자신보다 작은 서로 소인 수의 개수를 의미한다. n/φ(n) 의 값이 최대가 되기 위해서는 φ(n)의 값이 n대비 작을수록 유리하다. 피함수의 값이 작다는 말은 서로 소인 수의 개수가 작다는 것을 의미한다.

임의의 자연수 N을 소인수 분해한 결과가 이라고 가정해보자. 이 때 N과 서로 소가 아닌 수들은 a, b, c…의 각 소인수의 배수인 수들이다. 이러한 수들이 많으려면 소인수의 종류가 다양할수록 좋고, N 대비하여 소인수의 종류가 더 많아지려면 p, q, r .. 등의 값은 작을 수록 유리하다. 따라서 n/φ(n) 값이 최대가 되는 n은 소인수분해했을 때 각 소인수의 지수가 1이고, 소인수는 작은 것부터 소수들이 차례로 등장하게 된다.  따라서 2부터 연속된 소수들의 곱을 만들어나가면서 백만을 넘지 않는 시점까지 계산한다. 20미만의 소수를 모두 곱한 값은 970만 정도 되므로 20개의 소수만 있으면 되겠다.

소수 판별함수는 다른 문제에서도 많이 써봤으니까 여기서는 생략하겠다. (gist를 추가하니 참고해도 좋다.) 계산을 위한 코드는 다음과 같다.

# python3.6
limit = 1_000_000
result = 1
for p in [x for x in range(21) if is_prime(x)]:
  if result * p > limit:
    break
  result *= p
print(result)
## Wall time: 0 ns