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

Recommended Posts

Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
Functional programming in Python Project Euler 1
Project Euler 10 "Sum of Prime Numbers"
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Functional programming in Python Project Euler 2
Project Euler 11 "Maximum product in grid"
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python