Le nombre de pentagone est généré par «Pn = n (3n-1) / 2». Les 10 premiers termes sont
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
Est.
"P4 + P7 = 22 + 70 = 92 = P8". Mais la différence "70 - 22 = 48" n'est pas un pentagone.
À propos des paires pentagonales Pj et Pk,Considérez ce que la différence et la somme sont pentagonales.faites une différenceD = |Pk - Pj|Écrire.Trouvez la valeur minimale de la différence D.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
Après avoir créé une séquence de pentagones jusqu'au terme 2n, déterminez si la somme et la différence des pentagones du terme n et les pentagones des 1er à n termes sont tous deux des pentagones. fait. Puisqu'il a fallu du temps pour faire référence à l'attribut append, etc., l'attribut append et l'attribut add ont été placés dans les variables à l'avance. De plus, nous avons cherché à améliorer la vitesse en se référant à l'objet défini pour voir si les éléments sont inclus dans un ensemble prédéterminé.
En conséquence, nous avons d'abord trouvé un nombre dont la somme et la différence étaient pentagonales, mais nous n'avons pas pu confirmer qu'il était le plus petit.
def pe44():
start, stop = 1, 10**8
pen = ((n * ( 3*n - 1))//2 for n in xrange(start, stop))
p_list, p_set = [], set([])
ans = 10**10
i = 0
append = p_list.append
add = p_set.add
while 1:
append(pen.next())
append(pen.next())
add(p_list[2*i])
add(p_list[2*i+1])
d = search(p_list[i],p_list[:i+1],p_set)
if d:
min_d = min(d)
if min_d < ans:
found_answer(min_d)
ans = min_d
if ans < p_list[i+1] - p_list[i]:
break
i+=1
return ans
def found_answer(n):
print n
#@debug
def search(p1,p_list,p_set):
d = []
for p2 in p_list:
if (p1+p2 in p_set) and (p1-p2 in p_set):
#if (p1+p2 in p_list) and (p1-p2 in p_list):
d.append(p1-p2)
return d
pe44()
Recommended Posts