Project Euler > Problem 44 > Pentagon numbers (Java Solution)

Problem:

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?

Solution:

5482660

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 44
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */


public final class p044 implements EulerSolution {
 
 public static void main(String[] args) {
  System.out.println(new p044().run());
 }
 
 
 public String run() {
  long minD = -1;
  // For each upper pentagonal number index, going upward
  for (int i = 2; ; i++) {
   long pentI = pentagonalNumber(i);
   // If the next number down is more than a found difference, then conclude searching
   if (minD != -1 && pentI - pentagonalNumber(i - 1) > minD)
    break;
   
   // For each lower pentagonal number index, going downward
   for (int j = i - 1; j >= 1; j--) {
    long pentJ = pentagonalNumber(j);
    long diff = pentI - pentJ;
    // If the difference is at least as big as a found difference, then stop testing lower pentagonal numbers
    if (minD != -1 && diff >= minD)
     break;
    else if (isPentagonalNumber(pentI + pentJ) && isPentagonalNumber(diff) && (minD == -1 || diff < minD))
     minD = diff;  // Found a smaller difference
   }
  }
  return Long.toString(minD);
 }
 
 
 private static long pentagonalNumber(int x) {
  if (x <= 0)
   throw new IllegalArgumentException();
  return (long)x * (x * 3 - 1) >>> 1;
 }
 
 
 private static boolean isPentagonalNumber(long y) {
  if (y <= 0)
   return false;
  
  /* 
   * If y = pentagonalNumber(x) = x(3x-1) / 2,
   * then by the quadratic formula, the positive solution is x = (sqrt(24y + 1) + 1) / 6.
   * There exists a solution for x if and only if both of these conditions hold:
   * (24y + 1) is a perfect square, and sqrt(24y + 1) + 1 mod 6 = 0.
   * The second condition is equivalent to sqrt(24y + 1) = 5 mod 6.
   */
  long temp = y * 24 + 1;
  long sqrt = Library.sqrt(temp);
  return sqrt * sqrt == temp && sqrt % 6 == 5;
 }
 
}