Diophantine Equation

16
Mar
2013
Project Euler 140: Modified Fibonacci golden nuggets

Project Euler 140: Modified Fibonacci golden nuggets

Problem 140 of Project Euler is very much a continuation of the Problem 137, as we can see from the problem description

Consider 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, … .

For this problem we shall be concerned with values of x for which AG(x) is a positive integer.

The corresponding values of x for the first five natural numbers are shown below.

x AG(x)
(√5-1)/4 1
2/5 2
(√22-2)/6 3
(√137-5)/14 4
1/2 5

We shall call AG(x) a golden nugget if x is rational, because they become increasingly rarer; for example, the 20th golden nugget is 211345365.

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 →

Posted by Kristian in Project Euler, 6 comments
09
Mar
2013
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 (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.

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
02
Mar
2013
Project Euler 138: Special isosceles triangles

Project Euler 138: Special isosceles triangles

Problem 138 of Project Euler reads

Consider the isosceles triangle with base length, b = 16, and legs, L = 17.

By using the Pythagorean theorem it can be seen that the height of the triangle, h = √(172 – 82) = 15, which is one less than the base length.

With b = 272 and L = 305, we get h = 273, which is one more than the base length, and this is the second smallest isosceles triangle with the property that h = b ± 1.

Find ∑ L for the twelve smallest isosceles triangles for which h = b ± 1 and b, L are positive integers.

Continue reading →

Posted by Kristian in Project Euler, 9 comments
09
Jun
2012
Project Euler 100: Finding the number of blue discs for which there is 50% chance of taking two blue.

Project Euler 100: Finding the number of blue discs for which there is 50% chance of taking two blue.

So now we are at Problem 100 at Project Euler, you could call this an anniversary and I would have expected something extra difficult.  It took a while for me to crack the following problem

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)x(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 1012 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

Continue reading →

Posted by Kristian in Project Euler, 23 comments