p044.py

'''
Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. The first ten
pentagonal numbers are:

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

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference,
70 - 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and
difference are pentagonal and D = |Pk - Pj| is minimised;
what is the value of D?
'''

import common
import itertools

def pentagonal(n):
  return n * (3*n - 1) / 2

common.assertEquals([1, 5, 12, 22, 35, 51, 70, 92, 117, 145],
                    map(pentagonal, range(1,11)))

max_pentagonal = 0
cached_pentagonals = set()
def is_pentagonal(p):
  global max_pentagonal, cached_pentagonals
  while max_pentagonal < p:
    max_pentagonal = pentagonal(len(cached_pentagonals)+1)
    cached_pentagonals.add(max_pentagonal)
  return p in cached_pentagonals

common.assertEquals(True, is_pentagonal(92))
common.assertEquals(False, is_pentagonal(91))

def euler044():
  for i in itertools.count(1):
    pi = pentagonal(i)
    for j in range(1,i):
      pj = pentagonal(j)
      if is_pentagonal(pi + pj) and is_pentagonal(pi - pj): return pi-pj

common.submit(euler044(), expected=5482660)