Project Euler > Problem 94 > Almost equilateral triangles (Java Solution)

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).


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