오일러 프로젝트 60은 앞뒤로 이어붙여도 소수가 되는 특별한 관계를 갖는 소수끼리 모인 집합을 찾는 문제이다. 역시 시간이 관건이 되는 문제이다.
네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.
접근
여러 모로 까다로운 문제이다. 범위를 한정하기 어렵다는 것이 가장 큰 문제이다. 일단 2는 소수이지만 다른 소수 뒤에 붙여서 소수를 만들 수 없으므로 (2로 끝나는 짝수가 되므로) 제외하면 나머지 홀수인 소수들만 대상이 된다. 그리고 우리는 만들 수 있는 집합 중에서 원소의 합이 최소가 되는 경우를 우선 찾고자 한다. 따라서 가능한 작은 요소들로 위 조건을 만족하는 홀수의 부분집합을 다음과 같이 찾아보자.
- 정렬된 홀수인 소수의 집합을 P라고 한다. (P = {3, 5, 7, 11, … })
- 먼저 P에서 가장 작은 원소 3을 채택한다. 그리고 그 나머지 소수들에 대해서 차례로 “3A”, “A3” 이라고 각각 붙여 썼을 때 소수가 되는 A를 찾아나간다. 이렇게 3을 앞뒤로 붙여서 소수를 만들 수 있는 P의 부분집합을
이라고 하자.
- 마찬가지로 7을 선택해서 (5는 역시 뒤에 붙으면 5의 배수가 되기 때문에 조건을 충족할 수 없다), 다시 P의 다른 원소들을 차례로 이어붙여 소수를 만드는 부분집합을 찾을 수 있다. 이는
이 된다.
- 따라서
은 3과 7에 연결했을 때 두 경우 모두를 만족한다. 이는
의 원소 중에서 7에 대한 조건을 만족하는 부분집합이기도 하다.
- 다시
의 원소중에서 가장 작은 원소부터 채택하여 나머지 원소들의 앞뒤에 붙였을 때 조건을 만족하는 것을 찾아나갈 수 있다. 그 값을 S라 한다면 이 과정으로 필터링된 결과는
가 될 것이다.
- 이런 식으로 계속해서 필터링 되는 S, T, U.. 를 필터링해 나간다.
까지 구하게 된다면 이는 다섯개 소수를 골라잡았을 때 그 중 두 개를 서로 앞/뒤로 이어붙였을 때 항상 소수가 될 것이다.
- 단, 이 때는 P_n 들이 모두 무한 집합이라는 가정이 필요하다. 우리는 실제로 무한 집합을 다룰 수 없으므로 임의 자리수까지의 소수를 찾아놓고 그 중에서 시작한다.
- 만약 주어진 모집합에서 조건에 맞는 원소를 찾을 수 없다면, 최종적으로 추가한 n을 탈락 시키고 다음 번 소수로 재시도하는 백트래킹이 필요하다.
이 구현은 매우 복잡해 보이는데, 비슷한 동작을 계속 이어나가기 때문에 재귀로 구현했을 때 비교적 간단하게 풀 수 있을 것 같다. 일단 문제를 간단히 하기 위한 building block들을 준비해보자.
구현 (Swift)
먼저 숫자를 이어붙이는 작업에 대해서 생각해보자. Swift의 경우 문자열 > 더하기 > 다시 정수로 바꾸는 것보다는 로그를 이용해서 자리 수를 구하여 계산하는 쪽이 빠르게 처리된다.
func concat(_ a: Int, _ b: Int) -> Int {
/// 두 정수를 주어진 순서대로 연결한 새 정수를 리턴한다.
guard b > 0 else { return a }
let c = Int(log10(Double(b))) + 1
return a * Int(pow(10, Double(c))) + b
}
// 테스트함수
func test(_ a: Int, _ b: Int) -> Bool {
/// concat으로 앞뒤로 연결한 두 정수가 모두 소수인지 검사한다.
return isPrime(concat(a, b)) && isPrime(concat(b, a))
}
소수 검사 함수는 워낙 많이 썼으니, 그 구현은 생략하자. 이제 소수 부분 집합으로부터 조건에 맞는 집합을 찾아보자. 다음 함수 process
는 사실상 이 문제를 푸는 모든 로직을 포괄한다.
- 모든 대상이 되는 소수의 집합과 현재까지 몇 단계의 후보를 얻었는지를 인자로 받는다.
- 전달받은 집합으로부터 각 멤버 p와 이어붙이기 테스트에 통과한 P_q 를 얻는다.
- P_q로부터 LEVEL – 1 개가 모두 이어붙여지는 집합을 구하고, 여기게 p를 더하면 LEVEL개의 집합을 얻을 수 있다.
- LEVEL이 0이되면 더 진행할 필요 없이, 대상 집합이 답이된다.
- 만약 조건에 맞는 추가 원소 집합을 찾을 수 없으면 실패로 간주, 이전 레벨로 돌아가서 다음번 P_q의 멤버로 테스트한다.
구현은 다음과 같다.
func process(in xs: Set<Int>, level: Int) -> Set<Int>? {
guard level > 0 else { return xs }
for a in xs.sorted() {
var ys = xs.filter{ $0 != a && test($0, a) }
if ys.count < level - 1 {continue }
if var result = process(in: ys, level: level - 1) {
result.insert(a)
return result
}
}
return nil
}
3자리소수범위에서 찾아보고, 답이 없으면 자리수를 늘려가며 찾는다.
main: do {
var l = 4
while true {
let limit = Int(pow(10, Double(l))
let primes = Set(stride(from:3, through:limit, by:2))
if let result = process(in: primes, level: 5) {
print(result.reduce(0, +))
break
}
l += 1
}
}
Python 풀이
동일한 알고리듬으로 구성했다. 아무래도 Swift보다는 좀 느려서 소수 검사에 메모이제이션을 적용하면, 2초 가량 걸린다.
def memoize(f):
m = dict()
def i(n):
if n in m: return m[n]
r = f(n); m[n] = r
return r
return i
@memoize
def is_prime(n):
if n < 2: return False
if n in (2, 3): return True
if n % 2 is 0 or n % 3 is 0: return False
if n < 25: return True
k, l = 5, n**0.5
while k <= l:
if n % k is 0 or n % (k+2) is 0: return False
k += 6
return True
def test(a, b):
return is_prime(int(f"{a}{b}")) and is_prime(int(f"{b}{a}"))
def process(xs, level):
if level == 0 : return set()
for a in sorted(xs):
ys = {x in x for xs if x != a and test(a, x)}
if len(ys) < level - 1: continue
result = process(ys, level - 1)
if result is not None:
result.add(a)
return result
return None
def e60():
l = 4
while True:
limit = 10**4
primes = {x for x in range(3,limit,2) if is_prime(x) }
result = process(primes, 5)
if result is not None:
print(sum(result))
return
l +=1
%timeit e60()
# Wall time: 2.31s