Project Euler

Problem 44: Penatagon Numbers

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 are pentagonal and D = |P_k - P_j | is minimized; what is the value of D?

The Catch

How to check if a number is pentagonal.
How to make sure that D is minimized.

The Light

As in the discussion in Problem 42, solve the inverse function to check if an integer is pentagonal.
P(n) = t = n(3n - 1)/2
2t = 3n² - n
0 = 3n² - n - 2t
n = (1 + sprt(1 + 24t))/6 and
n = (1 - sqrt(1 + 24t) )/6 (discarded)

To make sure that the difference is minimized, for each pentagonal number p found, find the sum and difference of p with each and every pentagonal number a, with a < p. Stop at the first instance where both the sum and difference are pentagonal(i.e the difference D is minimized). This is because after this instance, the difference D will get larger as p and a get larger.

The Code

public class Problem44
{
  public static void main(String[] args)
  {
    boolean found = false;
    long j = 1;
	
    while(!found)
    {
      long Pj = j * (3*j - 1)/2;
      
      for(long k = j - 1; k > 0; k--)
      {
        long Pk = k * (3*k - 1)/2;
        if(isPent(Pj - Pk) && isPent(Pj + Pk))
        {
          found = true;
          System.out.println(Pj - Pk);
          break;
        }
      }
      j++;	  
    }	
  }
  
  public static boolean isPent( long t )
  {
    double tmp = (1.0 + Math.sqrt(1 + 24 * t)) / 6.0;
    return tmp == (long)tmp;
  }
}