Posts Tagged with "Brute Force"

Problem146

Project Euler 146: Investigating a Prime Pattern

Saturday, April 27, 2013

2 Comments

In Problem 146 of Project Euler we are working with primes again, and some quite big ones even. The problem reads The smallest positive integer n for which the numbers n2+1, n2+3, n2+7, n2+9, n2+13, and n2+27 are consecutive primes is 10. The sum of all such integers n below one-million is 1242490. What is the sum of all such integers n below 150 million? At first […]

Continue reading...
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...
problem141

Project Euler 141:Investigating progressive numbers, n, which are also square.

Saturday, March 23, 2013

12 Comments

Problem 141 of Project Euler proved to be just as difficult as the number of people who has actually solved it shows. The problem readsA positive integer, n, is divided by d and the quotient and remainder are q and r respectively. In addition d, q, and r are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.Some progressive numbers, such as 9 and 10404 = 1022, happen to also be perfect squares.Find the sum of all progressive perfect squares below one trillion (1012).I ended up getting the right idea when I was working out. I guess some times it really does help to do something else. In this problem it comes down to some really basic properties and insights so lets start with those

Continue reading...
problem137

Project Euler 137: Fibonacci golden nuggets

Saturday, February 23, 2013

6 Comments

I think that Problem 137 of Project Euler is a really fantastic problem since it has so many facets of how it can be solved. I will go through a one of them, and then link to a few other. The problem readsConsider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + ..., where Fk is the kth term in the Fibonacci sequenceWe shall call AF(x) a golden nugget if x is rational. Find the 15th golden nugget.I honestly don't know a whole lot about infinite series, and I am always quite intimidated by them. However, I know enough about them to know that there is something called a generating function which should be the keyword here.

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

9 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...
problem133

Project Euler 133: Repunit nonfactors

Saturday, January 26, 2013

4 Comments

Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10n) for any n. In fact the problem readsFind the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).I have found two methods for solving this. Both build upon the same principle which I will present first...

Continue reading...