Posts Tagged with "Algebra"

problem145

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

Saturday, April 20, 2013

1 Comment

In Problem 145 of Project Euler we move away from Geometry and over to number theory again, with a problem which readsSome 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 reversibleHow 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...
Problem144_featured

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

Saturday, April 13, 2013

10 Comments

Problem 144 of Project Euler is once again a geometry problem, just like the previous. However, it is completely different. The problem readsIn 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 = 100The 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).How many times does the beam hit the internal surface of the white cell before exiting?We will simply brute force our way through this problem, by calculating the laser beams path through the cell, and check if it hits the exit. In order to do that, we need to calculate how the laserbeam reflects. Once we know the angle of the reflecting beam, we can calculate the corresponding line, since we have the point of reflection. Once we have a line parameterization of the reflecting line, it is simply a matter of finding out where the line and the ellipse intersect. This will be the next point out laser beam hits. Confused yet? Don't be. I will elaborate on it. Lets start by finding the slope of the reflecting beam.

Continue reading...
Problem143

Project Euler 143: Investigating the Torricelli point of a triangle

Saturday, April 6, 2013

2 Comments

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 readsLet 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.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.After solving it, I can see why there are so few other people who have solved it. Because it was really difficult, and took a whole lot of research for me.

Continue reading...
problem142

Project Euler 142: Perfect Square Collection

Saturday, March 30, 2013

5 Comments

Problem 142 of Project Euler seems to be one in the easier end, at least if you aren't afraid of a little algebra. The problem readsFind the smallest x + y + z with integers x > y > z > 0 such that x + y, x - y, x + z, x - z, y + z, y - z are all perfect squares.I don't think we can manage to iterate over all possible values of x, y and z. So let us see if we can use the relations that has to be squares to something.

Continue reading...
problem139

Project Euler 139: Pythagorean tiles

Saturday, March 9, 2013

3 Comments

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 readsLet (a, b, c) 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.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?I will give you two different approaches to solving it.

Continue reading...
projecteuler135

Project Euler 136: Singleton difference

Saturday, February 16, 2013

1 Comment

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 readsThe positive integers, x, y, 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: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...
projecteuler135

Project Euler 135: Same differences

Saturday, February 9, 2013

10 Comments

In Problem 135 of Project Euler we have another nice number theory problem. The problem readsGiven the positive integers, x, y, 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.How many values of n less than one million have exactly ten distinct solutions?The first key insight which I missed for a while, is to notice that x,y and z is an arithmetic progression which means that we have that y = z + d and x = z + 2d.

Continue reading...
problem134

Project Euler 134: Prime pair connection

Saturday, February 2, 2013

5 Comments

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 readsIn 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.Based on the problem description it is rather easy to formulate this as linear congruence and then all we need to do, is to figure out how to solve that.

Continue reading...
problem123

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

Saturday, November 17, 2012

6 Comments

Problem 123 of Project Euler readsLet 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.Find the least value of n for which the remainder first exceeds 1010.A nice and short problem description which will also have a nice and short solution post since we solved Problem 120 which is very similar to this problem.

Continue reading...
uva294header

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

Saturday, August 4, 2012

5 Comments

Let us jump right into Problem 108 of Project Euler which readsIn the following equation x, y, and n are positive integers.1/x + 1/y = 1/n What is the least value of n for which the number of distinct solutions exceeds one-thousand?We could possibly brute force, but my guess is that it would take a rather long time to do so. So instead I started fiddling around with the equation to get some insight into the problem.

Continue reading...