오일러 프로젝트 49

오일러 프로젝트 49 번 문제는 서로 순열이면서 등차수열을 이루는 네 자리 소수 3개를 찾는 것이다. 이 문제는 간단할 것 같으면서도 엄청나게 귀찮은 요소들을 포함한다.

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

접근

서로 순열인 4자리 소수끼리 묶은 다음에, 각 묶음에서 등차수열인 세 소수가 있는 것을 골라낸다. 문제에서는 이러한 수열은 네 자리에서 두 개가 존재한다고 했다. 물론 4자리 소수가 적은 양은 아니지만, 백만 단위에 비해서는 한참 가뿐해보인다. 두 수가 순열인 것은 문자열로 만들어서 정렬¹하고 다시 문자열로 합친 것이 같기 때문에 이를 이용한다.
순열인 소수를 묶기 위해서는 간단하게 문자열을 키로 하고, 값을 정수리스트로하는 사전을 사용하기로 한다. 4자리 소수 전체에 대해서 키를 만들고, 키에 따라 사전내에서 분류하면 자동으로 순열인 소수들이 같은 리스트로 묶이게 된다. 이제 이렇게 묶인 사전의 값들에 대해서 길이가 3이상인 것들을 추려내어 답을 찾는다.

이 때 나이브하게 생각하면 길이가 3인 것들만 추리면 되지 않을까?했는데, 아쉽게도 아니다. 문제에 제시된 1487의 순열인 다른 소수도 존재한다! 다만 그 수는 다른 수와 등차수열을 못 이룰 뿐이다.

리스트 내에서 등차수열 찾기

만약 리스트의 원소가 3개라면, 크기순으로 가운데 원소를 두 배한 것이 다른 두 원소의 합과 같으면 바로 판별할 수 있다. 그런데, 리스트의 원소가 4개 이상이라면? 그 중 3개를 골라서 등차수열을 이루는지 확인해야 한다. 리스트내에서 순열을 뽑아내면서 체크할 것인지를 고민하다가 다음과 같은 방식으로 해결하기로 했다.

1. 일단 리스트에는 3개 이상의 원소가 있고, 이 중에서 a, b, c (크기 순)이 등차수열을 이루는 세 원소라 하자.
2. 그러면 b * 2 = a + c 이고 따라서 c = b * 2 – a 가 된다.
3. 리스트를 정렬한다.
4. 가장 작은 원소부터 a로 고정한다. 그리고 a는 등차수열을 찾을 때까지 끝에서 3번째요소까지 진행한다.
5. a의 바로 다음 값을 b라 한다. 그러면 c의 값을 구할 수 있는데, 이 때 c가 리스트에 있는지 검사한다.
6. c를 찾지 못하면 b를 다음 원소로 계속 옮겨가면서 찾는다. 여전히 찾지 못했다면 a를 그 다음 원소로 옮기고 다시 5로 돌아간다.

이 과정을 끝까지 반복했을 때 원소를 찾지 못했다면 리스트서는 등차수열을 발견할 수 없을 것이고, 찾는다면 즉시 중지하면 된다.이를 코드로 표현하면 다음과 같다.

def find_sequences(l):
  ## 등차수열은 크기순으로 a, b, c 라고 하자.
  l = sorted(l)
  for i, a in enumerated(l[:-2]): ## 우선 a고정. 끝에서 3번까지만
    remain = l[i+1]
    for b in remains: ## 다음 b 선택
      c = b * 2 - a
      if c in remain:
        print("".join(str(x) for x in (a, b, c)])
        return 

최종코드

소수체를 통해서 4자리 소수를 만들고, 같은 순열끼리 묶은 후, 길이 3이상인 그룹에 대해서 등차수열을 찾는 과정을 정리했다.

limit = 10_000
## 10_000 이하의 소수를 찾기위한 소수체
sieve = [False, False] + [True] * (limit - 1)
for i in range(2, int(limit**0.5 + 0.5)):
  if sieve[i]:
    sieve[i*2::i] = [False] * ((limit - i) // i)
## 네자리 소수 전체 목록
primes = [x for x in range(1000,10000) if seive[x]]
## 순열을 구분하기 위한 키 생성
def make_key(n):
  return "".join(sorted(str(n)))
## 리스트 내에서 등차수열 찾기
def find_sequences(l):
  l = sorted(l)
  for i, a in enumerate(l[:-2]):
    remain = l[i+1:]
    for b in remain:
      c = a * 2 - b
      if c in remain:
        print("".join(str(x) for x in (a, b, c)))
        return
def e49():
  d = {}
  for p in primes:
    key = make_key(p)
    if key not in d:
      d[key] = [p]
    else:
      d[key].append(p)
  targets = (x for x in d.values() if len(x) > 2)
  for l in targets:
    find_sequences(l)
e49()

좀 더 생각해보기

순열인 4자리 소수로 이루어진 등차수열의 등차는 3330이다. 그 이유를 밝힐 수 있다면, a를 고정하고 a+3330, a+6660 인 값이 순열이면서 소수라는 걸 검사해서 찾을 수도 있다.