Project Euler

Everything regarding Project Euler solutions.

Project Euler 267: Billionaire

Project Euler 267: Billionaire

It has been a long while since I solved any Project Euler problem. For some reason I read an article about it and someone references Problem 267, so I decided to take a look at it, and it sucked me in. The problem reads

You are given a unique investment opportunity.

Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.

Your return is double your bet for heads and you lose your bet for tails.

For example, if f = 1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125.

Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?

All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.

 

Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 146: Investigating a Prime Pattern

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 I thought I could just make a sieve up to 150 million and then check if the numbers were contained in that. However, rereading the problem I realized I was completely wrong. So in a pure brute force solution we would need to check 150 million values of n and up to 13 numbers for each, since we both need to check that the given numbers are prime. But also that the odd numbers inbetween are not prime. So potentially we have to check 1950 million numbers for primality, which is a moderately expensive operation. Continue reading →

Posted by Kristian in Project Euler, 7 comments
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 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 141:Investigating progressive numbers, n, which are also square.

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

Problem 141 of Project Euler proved to be just as difficult as the number of people who has actually solved it shows.  The problem reads

A positive integer, n, is divided by d and the quotient and remainder are q and r respectively. In addition dq, and r are consecutive positive integer terms in a geometric sequence, but not necessarily in that order.

For example, 58 divided by 6 has quotient 9 and remainder 4. It can also be seen that 4, 6, 9 are consecutive terms in a geometric sequence (common ratio 3/2).
We will call such numbers, n, progressive.

Some progressive numbers, such as 9 and 10404 = 1022, happen to also be perfect squares.
The sum of all progressive perfect squares below one hundred thousand is 124657.

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 →

Posted by Kristian in Project Euler, 22 comments
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
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 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, 10 comments
Project Euler 137: Fibonacci golden nuggets

Project Euler 137: Fibonacci golden nuggets

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 reads

Consider the infinite polynomial series AF(x) = xF1 + x2F2 + x3F3 + …, where Fk is the kth term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, … ; that is, Fk = Fk-1 + Fk-2, F1 = 1 and F2 = 1.

For this problem we shall be interested in values of x for which AF(x) is a positive integer.

Surprisingly AF(1/2)  =  (1/2).1 + (1/2)2.1 + (1/2)3.2 + (1/2)4.3 + (1/2)5.5 + …
   =  1/2 + 1/4 + 2/8 + 3/16 + 5/32 + …
   =  2

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

x AF(x)
√2-1 1
1/2 2
(√13-2)/3 3
(√89-5)/8 4
(√34-3)/5 5

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

Find the 15th golden nugget.

Continue reading →

Posted by Kristian in Project Euler, 7 comments