##
**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 .

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