콘텐츠로 건너뛰기
Home » 오일러 프로젝트 49

오일러 프로젝트 49

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다. 세 수는 모두 소수입니다. 세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다. 1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다. 그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=49

접근

문제에서 제시한 범위가 4자리수 (1234 ~ 9876) 내에 있기 때문에 범위는 제법 좁은 편이지만, 효과적으로 조건에 맞는 값을 찾도록 하는 것이 제법 성가시다. 일단 답을 찾는 과정을 다음과 같이 확인할 수 있다.

  1. 모든 후보가 되는 수는 소수이다. 따라서 1,000 이상 10,000 이하의 소수를 소수체를 사용하여 모두 구한다.
  2. ‘5617’, ‘7561’ 등 같은 숫자의 순열인 것들을 각각의 리스트로 묶는다. 이를 위해서는 각 수의 숫자들을 크기 순으로 정렬한 최소순열을 기준으로 구분하여, 하나의 사전에 (최소순열, 순열리스트)의 형식으로 저장한다.
  3. 사전에 저장된 값 중에서 길이가 3이상인 것들만 대상으로, 소수들의 등차수열이 존재하는지 찾는다.

먼저 아래와 같이 소수체를 만드는 함수와 최소순열을 구하는 함수를 작성한다. 

from functools import reduce 

def sieve(n: int) -> list[int]:
  s = [False] * 2 + [True] * (n - 1)
  for i in range(int(n ** 0.5 + 1.5)):
    if s[i]:
      s[i+i::i] = [False] * ((n - i) // i)
  return [i for i, x in enumerate(s) if x]


def make_key(n: int) -> str:
  return ''.join(sorted(list(str(n))))

등차수열 찾기

만약 4개나 5개가 같은 순열일 때, 이 중 3개가 등차수열을 이루는지 확인하는 방법은 무엇일까? 정렬된 리스트에서 2개를 고르고 그 차이와 고른 두 개의 수 중 큰 수를 더한 값이 다시 그 리스트에 있는지를 검사하는 방법을 사용할 수 있다. 아니면 성능은 조금 떨어질지 몰라도, n 개 중에서 3개의 조합을 구하고 그 세 수가 등차수열인지를 찾으면 된다.

전자의 방법

def test(xs: list[int]) -> bool:
  for i, x in enumerate(xs[:-2]):
    for j, y in enumerate(xs[i+1:-1]):
      if (2 * y - x) in xs:
        return [x, y, y * 2 - x]
  return None

좀 더 복잡하고 세련된 방법으로는, 3 개의 수를 고르는 조합에서 등차수열을 찾는 것이다. 

def combinations(xs, n=3):
  def helper(head, tail, k):
    if k == 0:
      return [head]
    res = []
    for (i, x) in enumerate(tail):
      res.extend(helper([*head, x], tail[i+1:], k-1))
    return res
  return helper([], xs, n)

def test(xs):
  for a, b, c in combinations(xs, 3):
    if b * 2 == c - a:
      return [a, b, c]
  return None

문제를 푸는데는 어떤 방식을 써도 상관 없다. 


seqs = {}
# 소수들을 같은 순열끼리 묶기
for p in filter(lambda x: x > 99, sieve(10000)):
  seqs.setdefault(shrink(p), list()).append(p)

# 각각 순열리스트에서 등차수열이 있으면 출력하기 

for ds in seqs.values():
  if len(ds) < 3:
    continue
  res = test(ds)
  if res:
    print(''.join(map(str, res)))

이 코드에서는 전수 검사를 하고, 두 개의 답을 찾은 후에도 중간에 멈추지 않는다. 워낙에 금방 끝나는 작업이라 따로 루프를 탈출하지 않았다.

좀 더 생각해보기

문제에서 제시한 순열의 3개 소수 외에 이 문제의 정답도 공차가 3330으로 동일한 순열인데, 이게 특별한 의미가 있는 것인지 참 공교롭게 느껴진다. 위 코드를 조금 수정하면 순열이면서 등차수열을 이루는 4개의 소수 조합을 1개(83987, 88937, 93887, 98837)찾을 수 있는데, 이 때의 공차는 4950으로, 3330은 우연한 경우인 것 같다.

참고로 순열인 수들끼리의 차는 무조건 9의 배수가 된다.

태그: