**Problem:**

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

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