Problem Description

Pentagonal numbers are generated by the formula, P_n=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 P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference is pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

Analysis

How many pentagonal numbers are required to search through to solve the problem? We wrote the following program and started with 10,000 pentagonal numbers and, after finding the correct answer, adjusted the requirement down to 2,400. When the problem asks for D = |P_k − P_j| to be minimized it simply means the smallest pair which, by our method, is the first occurrence found.

A set (hashable) is used to both hold the pentagonal numbers and to check if a number is pentagonal. All that’s left is to permute the pairs and check that the difference and sum are pentagonal numbers.
Runs < 2 seconds in Python.

pent = set( n * (3*n - 1) / 2 for n in range(2,2400) ) 
 
def pe44():
  for pj in pent: 
    for pk in pent: 
      if pj - pk in pent and pj + pk in pent: 
        return pj - pk
 
print "Answer to PE44 = ",pe44()

So, a more challenging program might be to solve the problem without having to guess at how many pentagonal numbers are required. That would require a function to determine if a number is pentagonal. (When the equation (√(1 + 24 · n) + 1) / 6 evaluates to an integer, n, is a pentagonal number.)

It turned out to be an interesting discovery and took longer to find an answer. But, as luck would have it, was very helpful for solving problem 45.

Solution

Runs < 6 seconds in Python.

from math import sqrt
 
def is_pentagonal(n):
  p = ( sqrt(1 + 24*n) + 1 ) / 6
  return p==int(p)
 
def pe44():
  i=0;
  pent = [1]
  while True:
    i+=1
    pent.append( i * (3*i - 1) / 2 )
    for j in range(2, len(pent)-1):
      if is_pentagonal(pent[i]-pent[j]) and is_pentagonal(pent[i]+pent[j]):
        return pent[i]-pent[j]
 
print "Answer to PE44 = ",pe44()

Comments

See Problem 45.