Algebra

Project Euler 145: How many reversible numbers are there below one-billion?

Project Euler 145: How many reversible numbers are there below one-billion?

In Problem 145 of Project Euler we move away from Geometry and over to number theory again, with a problem which reads

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (109)?

This one is insanely easy to write a brute force method and that is the first thing I did. However, as we shall see there is a more analytic approach to the problem as well. Continue reading →

Posted by Kristian in Project Euler, 5 comments
Project Euler 144: Investigating multiple reflections of a laser beam.

Project Euler 144: Investigating multiple reflections of a laser beam.

Problem 144 of Project Euler is once again a geometry problem, just like the previous. However, it is completely different. The problem reads

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?

Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 143: Investigating the Torricelli point of a triangle

Project Euler 143: Investigating the Torricelli point of a triangle

Problem 143 of Project Euler is a notorious problem. Notorious for having the fewest correct answers per time it has been released. If you sort by number of solvers, you will see a pretty good correlation between problem number and place on that list. However, this problem is moved quite a bit down that list. The problem reads

Let ABC be a triangle with all interior angles being less than 120 degrees. Let X be any point inside the triangle and let XA = p, XB = q, and XC = r.

Fermat challenged Torricelli to find the position of X such that p + q + r was minimised.

Torricelli was able to prove that if equilateral triangles AOB, BNC and AMC are constructed on each side of triangle ABC, the circumscribed circles of AOB, BNC, and AMC will intersect at a single point, T, inside the triangle. Moreover he proved that T, called the Torricelli/Fermat point, minimises p + q + r. Even more remarkable, it can be shown that when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO also intersect at T.

If the sum is minimised and a, b, c, p, q and r are all positive integers we shall call triangle ABC a Torricelli triangle. For example, a = 399, b = 455, c = 511 is an example of a Torricelli triangle, with p + q + r = 784.

Find the sum of all distinct values of p + q + r ≤ 120000 for Torricelli triangles.

Continue reading →

Posted by Kristian in Project Euler, 4 comments
Project Euler 139: Pythagorean tiles

Project Euler 139: Pythagorean tiles

In Project Euler There are loads of problems that end up with a number theoretic solution. Problem 139 is no exception to that.  The problem reads

Let (abc) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 136: Singleton difference

Project Euler 136: Singleton difference

Problem 136 of Project Euler can be solved in a very easy way, and a very fast way. So lets look at the problem and dive right into the problem which reads

The positive integers, xy, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation,x2 – y2 – z2 = n, has exactly one solution when n = 20:

132 – 102 – 72 = 20

In fact there are twenty-five values of n below one hundred for which the equation has a unique solution.

How many values of n less than fifty million have exactly one solution?

So this sounds a bit like Problem 135? Well it is a lot like that, and this is where we will get out easy solution from. Continue reading →

Posted by Kristian in Project Euler, 3 comments
Project Euler 135: Same differences

Project Euler 135: Same differences

In Problem 135 of Project Euler we have another nice number theory problem. The problem reads

Given the positive integers, xy, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2 – y2 – z2 = n, has exactly two solutions is n = 27:

342 – 272 – 202 = 122 – 92 – 62 = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

Continue reading →

Posted by Kristian in Project Euler, 13 comments
Project Euler 134: Prime pair connection

Project Euler 134: Prime pair connection

With a little help from Wikipedia I found Problem 134 of Project Euler rather easy to solve.  Well it was easy after solving some issues I had with integer overflows and several other bugs. But anyway, the problem reads

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ΣS for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

Continue reading →

Posted by Kristian in Project Euler, 5 comments
Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

Project Euler 123: Determining the remainder when (pn − 1)^n + (pn + 1)^n is divided by pn^2

Problem 123 of Project Euler reads

Let pn be the nth prime: 2, 3, 5, 7, 11, …, and let r be the remainder when (pn-1)n + (pn+1)n is divided by pn2.

For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.

Project Euler 108: Solving the Diophantine equation 1/x + 1/y = 1/n.

Let us jump right into Problem 108 of Project Euler which reads

In the following equation xy, and n are positive integers.

For n = 4 there are exactly three distinct solutions:

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of problem 110; it is strongly advised that you solve this one first.

Continue reading →

Posted by Kristian in Project Euler, 8 comments