오일러 프로젝트 73

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

n과 d가 양의 정수이고 n < d 인 분수 n/d을 GCD(n, d) = 1 일 때, 기약 진분수라 부르기로 합니다. d < 8 인 기약 진분수를 커지는 순으로 늘어놓으면 아래와 같습니다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

여기서 보듯이 1/3과 1/2사이에는 기약 진분수가 세 개 있습니다. 그러면 d <= 12000 일 때, 1/3과 1/2 사이에는 몇 개의 기약 진분수가 있습니까?

접근

이 문제는 임의의 기약 진분수를 x/y 로 두었을 때, y가 2x보다는 크고 3x보다는 작은 영역에서 서로소가 되는 케이스를 세면된다. 범위가 12000이하의 값이므로 문제 그대로를 풀면 된다.  간단한 GCD 구하는 함수를 만든 다음, 문제 그대로의 로직을 정직하게 구현하면 다음과 같다.

//// Swift 4.0

func gcd(_ a: Int, _ b: Int) -> Int {
  return b == 0 ? a : gcd(b, a % b)
}

timeit {
  var c = 0
  let limit = 12000
  for x in 2...(limit/2) {
    for y in (x*2+1)..<(x*3) where y <= limit {
      if gcd(y, x) == 1 { c += 1 }
    }
  }
  print(c)
}

이 코드의 풀이는 서글프기 그지없는 2010 MID 맥북에서 약 1.9초 내외로 답을 구하게 된다. 하지만 파이썬에서 동일한 코드로 체크하면 어떨까?

 파이썬으로 구현했을 때

def gcd(n, m):
  return n if m is 0 else gcd(m, n % m)

def f73():
  c, lmt = 0, 12_000
  for x in range(2, lmt//2+1):
    for y in range(x*2+1, x*3+1):
      if > lmt:
        break
      if gcd(y, x) == 1:
        c += 1
  print(c)

%time f73()
# wall time: 56.2s

또 다른 접근법

오마이갓.  성능이 너무 안나온다. 다르게 접근해보자. 분모가 N 이하인 0~1 사이의 기약 진분수들의 수열을 페리수열이라고 한다. 페리 수열 내의 특정한 두 분수가 있을 때, 그 사이의 분수는 양 옆의 분수의 분모와 분자를 각각 더한 값이 된다. 예를 들어 1/3 과 1/2 사이의 수는 (1+1)/(3+2) 하여 2/5 가 되는 식이다. 이런식으로 분모가 12000을 넘지 않을 때까지 사이의 값을 촘촘히 채워나가서 페리 수열의 리스트를 생성한 후, 이 리스트의 길이 – 2 (1/3, 1/2은 제외하므로) 를 구해보자.

참고로, 생성해야하는 리스트는 꼭 분수를 원소로 가질 필요가 없다. 정수 두개의 튜플로 대신하겠다. 또한 리스트의 특정한 위치에 원소를 삽입하는 것은 슬라이스 문법을 이용하면 가장 빠르게 처리할 수 있다.

def f72_2():
  L = [(1,3), (1,2)]
  i, m = 1, 2
  while i < m:
    while True:
      a, b = L[i-1]
      c, d = L[i]
      if b+d > 12_000:
        break
      L[i:i] = [(a+c, b+d)]
      m += 1
    i += 1
  print(c - 2)

느려터진 맥북에서도 이 결과는 12초대의 나름 개선된 퍼포먼스를 보여준다. 일단 이정도에서 만족하기로 하자.

보너스 – 줄리아

공학 계산용으로 디자인된 Julia의 경우, 내장된 GCD 함수가 매우 성능이 좋고, 이러한 수학문제에 특히 잘 작동할 수 있다고한다.  최초의 알고리듬을 그대로 사용하여 풀어보면 다음과 같다.

function f73()
  c, lmt = 0, 12000
  for x = 2:Int(floor(lmt/2 + 0.5))
    for y = 2x+1:3x
      y >= limit && break
      if gcd(y, x) == 1
        c += 1
      end
    end
  end
  c
end

@time f73()

수행 결과는 0.82초로 컴파일된 Swift 코드의 성능을 압도한다.