Project Euler > Problem 144 > Investigating multiple reflections of a laser beam. (Java Solution)

Problem:

In laser physics, a "white cell" is a mirror system that acts as a delay line for the laser beam. The beam enters the cell, bounces around on the mirrors, and eventually works its way back out.

The specific white cell we will be considering is an ellipse with the equation 4x2 + y2 = 100

The section corresponding to [−]0.01 [≤] x [≤] +0.01 at the top is missing, allowing the light to enter and exit through the hole.

The light beam in this problem starts at the point (0.0,10.1) just outside the white cell, and the beam first impacts the mirror at (1.4,-9.6).

Each time the laser beam hits the surface of the ellipse, it follows the usual law of reflection "angle of incidence equals angle of reflection." That is, both the incident and reflected beams make the same angle with the normal line at the point of incidence.

In the figure on the left, the red line shows the first two points of contact between the laser beam and the wall of the white cell; the blue line shows the line tangent to the ellipse at the point of incidence of the first bounce.

The slope m of the tangent line at any point (x,y) of the given ellipse is: m = [−]4x/y

The normal line is perpendicular to this tangent line at the point of incidence.

The animation on the right shows the first 10 reflections of the beam.

How many times does the beam hit the internal surface of the white cell before exiting?

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