MathBlog
A man's journey through the wonderful world of Math and ProgrammingPosts Tagged with "C#"
Project Euler 146: Investigating a Prime Pattern
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...
Project Euler 145: How many reversible numbers are there below one-billion?
Saturday, April 20, 2013
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...
Project Euler 144: Investigating multiple reflections of a laser beam.
Saturday, April 13, 2013
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...
Project Euler 143: Investigating the Torricelli point of a triangle
Saturday, April 6, 2013
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...
Project Euler 142: Perfect Square Collection
Saturday, March 30, 2013
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...
Project Euler 141:Investigating progressive numbers, n, which are also square.
Saturday, March 23, 2013
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...
Project Euler 140: Modified Fibonacci golden nuggets
Saturday, March 16, 2013
Problem 140 of Project Euler is very much a continuation of the Problem 137, as we can see from the problem descriptionConsider the infinite polynomial series AG(x) = xG1 + x2G2 + x3G3 + ..., where Gk is the kth term of the second order recurrence relation Gk = Gk-1 + Gk-2, G1 = 1 and G2 = 4; that is, 1, 4, 5, 9, 14, 23, ... .We shall call AG(x) a golden nugget if x is rational. Find the sum of the first thirty golden nuggets.In Problem 137 I mentioned in the end that the problem could be solved using a Diophantine equation. This is exactly the way I will go for this problem.
Continue reading...
Project Euler 139: Pythagorean tiles
Saturday, March 9, 2013
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...
Project Euler 138: Special isosceles triangles
Saturday, March 2, 2013
Problem 138 of Project Euler readsFind ∑ L for the twelve smallest isosceles triangles for which h = b ± 1 and b, L are positive integers.The key to solving this problem is definitively to only consider the rightangled part of the triangle, such that you get a triangle consisting of one of the sides with length L, h and half the base (which I will denote x).I started out by figuring out that solutions would be primitive pythagorean triplets which we have worked with in Problem 9 among other places. So I tried to build a solution where I check to see if the triplets fulfill the condition that 2x ± 1 = h. However, I quickly ran into the fact that the solution would take forever to complete. So I had to take a step back and try another approach.
Continue reading...Project Euler 137: Fibonacci golden nuggets
Saturday, February 23, 2013
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...- Taking a break
- Project Euler 146: Investigating a Prime Pattern
- Project Euler 145: How many reversible numbers are there below one-billion?
- UVa Online Judge New Platform
- Project Euler 144: Investigating multiple reflections of a laser beam.
- Project Euler 143: Investigating the Torricelli point of a triangle
- Project Euler 142: Perfect Square Collection
- Project Euler 141:Investigating progressive numbers, n, which are also square.
- Project Euler 140: Modified Fibonacci golden nuggets
- Project Euler 139: Pythagorean tiles
- Son-Huy TRAN: I found that if 1 + a + b is prime, so : 1 + a + b > 1 => a + b > 0Because b is prime so b > 0, so if a < 0 : |a| < |b|So ...
- Jevon Jaconi: late arrival to the party and now it ends; that's my luck - j/k - have a good one and look forward to reading it again soon!;...
- Jean-Marie Hachey: Hi Kristian,Thank you very much for all the work done on your blog. Impressive production. Highly appreciated.Jeg takker dem meget, Merci b...
- Bjarki Ágúst: This is one of my favorite problems. I solved it very similarly. Given [latex]p_1[/latex] and [latex]p_2[/latex], I wanted to find an integer [latex]x...
- rebr: You can do this even in one single loop: int sundays = 0; for(DateTime date = new DateTime(1901, 1, 1); date.Date <= new DateTime(2000, 12, 31).D...
- Prashant: I see. That helps. Thanks again!...
Saturday, April 27, 2013
2 Comments