콘텐츠로 건너뛰기
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 shrink(n: int) -> int:
  '7528 -> 2578'
  res = []
  while n > 0:
    n, e = divmod(n, 10)
    res.append(e)
  return reduce(lambda x, y: x * 10 + y, sorted(res))

등차수열 찾기

리스트 내에서 등차수열을 어떻게 찾을 수 있을까? 바로 이웃한 순서대로 등차수열을 이룬다는 보장이 없기 때문에 이 중 루프를 돌면서 검사한다.

  1. a1, a2, a3,…, ak로 이어지는 수열에서 앞에서 순서대로 ai를 구한다. (i = 1, 2, 3,…, k-2)
  2. i < j 인 j를 작슨 순서부터 aj를 선택하여 d = (aj– ai) 을 구한다. 그런 다음 aj + d 가 리스트에 속해있는지 확인한다.
  3. 조건을 만족하는 값이 리스트에 있다면 순열인 세 소수가 등차수열을 이루는 것이 확인된다.
  4. 2~3에서 등차수열을 확인할 수 없다면 i = i + 1 한 후 2로 돌아간다.

위에서 작성한 함수를 사용하여 4자리 소수들을 모두 구하고, 이들을 같은 순열끼리 하나의 리스트에 묶어준다. (각 리스트는 이미 정렬된 상태로 만들어진다.)

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

# 각 순열리스트에서 등차수열 찾기
for ds in seqs.values():
  if len(ds) < 3:
    continue
  for i, x in enumerate(ds[-2:]):
    for y in ds[i+1:-1]:
      if (y * 2 - x) in ds:
        print(f"{x}{y}{y * 2 -x}")

이 코드에서는 1개의 경우를 찾은 후에 즉시 종료하지 않는데, 그렇더라도 검사해야하는 범위가 매우 좁기 때문에 수 ms 정도에서 연산이 끝난다.

좀 더 생각해보기

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

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

%d 블로거가 이것을 좋아합니다: