Project Euler 60をPythonでやってみる

問題60

英語
https://projecteuler.net/problem=60
日本語
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060

解答60

今回は難しかったです。
回答もあまり良いものではないかもしれません。
特に難しいのは最小性で答えが見つかっただけでは確認しきれません。

アルゴリズムに関しては次の記事を参考にしました。
https://tasusu.hatenablog.com/entry/20121119/1353331189

記事と同じようにグラフを作り、サイズ５のクリークを見つけるアルゴリズムを使いました。

ただこのアルゴリズムには問題点があります。
それはグラフの頂点となる素数の上限を決める必要があることです。
この上限値が低いと答えを確定できなかったりそもそも答えが見つからなかったりします。
逆に上限値を大きくしすぎるとグラフを作る計算量が大きくなり過ぎてしまいます。
今回は大体の答えがわかっていたため、この上限値を適切な30000と取りましたが、適切な上限値を与えないと良い働きをしないアルゴリズムになってしまいました。

コードは次のようになります。

ProjectEuler60.py

import sympy as sym
import math
import itertools


def is_Prime_Pairs(num1,num2):
    a = int(str(num1) + str(num2))
    if not (sym.isprime(a)):
        return False
    b = int(str(num2) + str(num1))
    return sym.isprime(b)

def del_vertex(edge_dic):
    dic = {prime:prime_set for prime,prime_set in edge_dic.items() if len(prime_set)>3} #次数3以下のvertexを削除
    return {prime: {q for q in prime_set if q in dic.keys()} for prime, prime_set in dic.items()}

def sum_clique(edge_set,p,clique_set):
    global ans_min
    next_clique_set = clique_set|{p}
    if len(next_clique_set) == 1:
        next_set = edge_dic[p]
    else:
        next_set = edge_dic[p] & edge_set

    if len(next_set) < 5-len(next_clique_set):
        return

    if len(next_clique_set) == 4:
        ans = sum(next_clique_set) + min(next_set)
        if ans_min == 0 or ans < ans_min:
            ans_min = ans
            # print(ans_min)
            return
    sort_next = sorted([x for x in next_set if x > max(next_clique_set)])
    for q in sort_next:
        sum_clique(next_set,q,next_clique_set)
    return



num_max =30000
primes = {i for i in sym.primerange(3,num_max)}
primes.remove(5) #5はどこともedgeを持たない
edge_dic = {i:set() for i in primes}

# グラフ作成
for p in primes:
    for q in (q for q in primes if q > p):
        if is_Prime_Pairs(p, q):
            # print((p,q))
            edge_dic[p].add(q)
            edge_dic[q].add(p)
print("Phase1")

# 次数3以下のvertexを削除
edge_dic = del_vertex(edge_dic)
print("Phase2")
# 素数の和が最少のクリークを探す
keys = sorted(edge_dic.keys())
ans_min = 0
for p in keys:
    if ans_min > 0 and p > ans_min:
        break
    sum_clique(set(),p,set())

print(ans_min)

62.598 seconds
グラフ作成だいたいが60sです。