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;
 }
 
}


No comments :

Post a Comment

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact