오일러 프로젝트 73

오일러 프로젝트 73번 문제는 기약진분수에 대한 문제이다. 이전 두 문제에서 오일러 피함수와 관계한 기약 진분수의 문제는 악몽과 같은 수행 시간을 보였는데, 이 문제는 그나마 스케일이 조금 작아서 그다지 어렵지 않다.

오일러 프로젝트 73 더보기

오일러 프로젝트 72

오일러 프로젝트 72 번 문제는 여태껏 나왔던 문제에서의 최고 난이도를 또 한 번 갱신했다. 오일러 피 함수(\phi )의 1에서 100만까지의 자연수에 대한 피함수 값의 합을 구해야하는 문제이며, 피 함수를 빠르게 작성하는 것이 얼마나 고된(?)일인지 알고 있다면 이 문제를 brute force로 푸는 것은 정말 답이 없다는 점에서 마음을 단단히 먹어야 한다.

오일러 프로젝트 72 더보기

프로젝트 오일러 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)
2112
31, 221.5
41, 322
51, 2, 3, 441.25
61, 523
71, 2, 3, 4, 5, 661.1666…
81, 3, 5, 742
91, 2, 4, 5, 7, 861.5
101, 3, 7, 942.5

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

임의의 자연수 N을 소인수 분해한 결과가 a^{p} \times b^{q} \times c^{r} ...이라고 가정해보자. 이 때 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

오일러 프로젝트 70

어느덧 오일러 프로젝트 풀이를 포스팅한게 70번째에 다다랐다. 점점 강려크한 난이도의 문제들이 나오면서 한 회 한 회 포스팅이 정말 쉽지 않다. 오일러 프로젝트 70 번 문제도 오일러 피(phi) 함수에 대한 내용이다. 이번에는 피함수의 값이 원래 값과 순열이 되는 조금 특별한 케이스를 찾는 문제이다.

오일러 프로젝트 70 더보기

오일러 프로젝트 68

오일러 프로젝트 68 번은 특별한 마방진에 관한 문제이다. 문제에 그림이 등장하기 때문인지 (한국어 사이트 기준으로) 풀이 수도 많지 않고, 포럼에 등록된 답변도 많지 않지만, 문제의 조건을 유심히 살펴보면 시험해야 하는 경우의 수를 많이 줄일 수 있고, 코드의 실행 시간 역시 그리 길지 않은 평이한 난이도를 가지고 있다.

오일러 프로젝트 68 더보기