Project Euler 44

problem

Pentagonal numbers are generated by Pn = n (3n-1) / 2. The first 10 terms are

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

Is.

P4 + P7 = 22 + 70 = 92 = P8. But the difference 70 --22 = 48 is not a pentagonal number.

About the pentagonal pair Pj and Pk,Consider what the difference and sum are pentagonal numbers.Make a differenceD = |Pk - Pj|Write.Find the minimum value of the difference D. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044

Answer

After creating a sequence of pentagonal numbers up to the 2n term, determine whether the sum and difference of the pentagonal number of the n term and the pentagonal numbers of the 1st to n terms are both pentagonal numbers. did. Since it took time to refer to the append attribute, etc., the append attribute and add attribute were put in the variables in advance. In addition, we aimed to improve the speed by referring to the set object to see if the elements are included in the predetermined set.

As a result, we first found a number whose sum and difference were pentagonal numbers, but we could not confirm that it was the smallest.

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