Projet Euler 44

problème

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

Répondre

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()