오일러 프로젝트 70

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

오일러 피(phi) 함수 φ(n)은 n보다 작거나 같은 자연수 중 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어 9이하에서 9와 서로 소인 자연수는 1,2,4,5,7,8 이므로 φ(9) = 6 입니다. 또 1은 어떤 자연수와도 서로 소이므로 φ(1) = 1 입니다.

φ(87109)의 값은 79180인데, 흥미롭게도 79180은 87109로 만들 수 있는 순열 중 하나입니다. 1 < n < 107 이고, φ(n)이 n의 순열이 되는 수 중에서 n/φ(n)이 최소인 n은 얼마입니까? (http://euler.synap.co.kr/prob_detail.php?id=70)

접근

이번에는 천만까지의 범위를 대상으로 한다. 따라서 phi 함수를 구현해서 답을 찾겠다고 나서는 것은 올바른 접근이 아니니 다른 방법을 강구해보아야 한다. 이번에는 n/φ(n)이 최소가 되는 케이스를 찾아야 한다. 이는 φ(n)이 크면 클수록 좋다는 전제가 있다.  φ(n)이 크다는 것은 자신 이하의 수 중에서 서로 소인 수가 많다는 것이고, 이는 해당 값을 소인수 분해했을 때, 중복에 상관없이 소인수의 개수가 작아야 한다는 것을 말한다.

일반적으로 가장 작은 소인수 개수를 갖는 것은 소수이다. 소수 p에 대해 φ(p) = p – 1 인데 (왜냐하면 자기 자신하고만 서로 소가 아니니까) 인접한 두 자연수가 서로 순열 관계에 있을 수는 없으므로1 최소한 φ(n)이 큰 n이 될 수 있는 케이스는 소수 두 개의 곱이다.

앞서, 소수 p에 대해서 φ(p) = p –  1 이라고 했다. 만약 어떤 수 n이 두 소수 p, q의 곱이라면 (이 때 n의 소인수 분해는 p * q 이다.) 앞의 성질에 의해 φ(n) = (p – 1)(q – 1)이 된다. 따라서 \frac{n}{\phi(n)} = \frac{n}{(p - 1)(q - 1)}이 최소가 되기 위해서는 (p – 1), (q – 1)의 거리가 가까울 수록 (n이 완전제곱수에 근접할 수록) 유리하다.

n의 범위는 천만(10,000,000) 미만의 자연수이므로 이 값은 천만의 제곱근인 3000 언저리에 있을 가능성이 높다. 따라서 2~6,000 사이의 소수 중에 두 개를 골라, (p – 1)(q – 1)이 (p * q)의 순열 (이 때, p * q 가 천만 미만이어야 한다)인 경우를 찾고, 그 중에 n/φ(n)이 최소가 되는 케이스를 찾으면 된다.

풀이

let primes: [Int] = {
  let limit = 6000
  var s = [false, false] + Array(repeating: true, count: limit-1)
  for i in 2..<(Int(sqrt(Double(limit)) + 0.5)) where s[i] {
    stride(from:i*2, through:limit, by:i).forEach{ s[$0] = false }
  }
  return (2...limit).filter{ s[$0] }
}()

var result: (Double, Int) = (10_000_000, 0)
for p in primes {
  for q in primes {
    guard case let n = p * q, let pn = (p - 1)*(q - 1),
    n < 10_000_000 else { break }
    if String(n).utf8.sorted() == String(pn).utf.sorted() {
      if case let r = Double(n) / Double(pn), r < result.0 { result = (r, n) }
    }
  }
}
print(result.1)

Swift에서는 숫자와 문자열 사이를 변환하는 것이 좀 부담스럽다. 특히 순열여부 판정을 위해서는 숫자를 문자열로 바꾼 다음, 정렬하여 비교해야 하는데, 이 과정이 제법 부담스러워서 파이썬보다 느리다. (컴파일 하지 않고 스크립트로 실행했을 때) 그나마 이 경우에 사용할 수 있는 팁은 다음과 같다.

  1. "\(x)" 와 같은 내삽 문법보다는 명시적으로 String(n)과 같이 문자열로 바꾸는 편이 성능이 좋다.
  2. 정렬된 상태를 비교만 하면 되는 경우, chracters.sorted() 대신에 utf8.sorted()를 쓰는 편이 훨씬 빠르다.

 

그외에는 특별한 내용이 없는 코드이므로, 파이썬 풀이는 생략한다.


  1. 순열 관련한 이전 문제에서도 언급했지만, 순열 관계에 있는 두 수는 9의 배수만큼 차이난다.