Algebra

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
Project Euler 94: Investigating almost equilateral triangles with integral sides and area.

Project Euler 94: Investigating almost equilateral triangles with integral sides and area.

I can realy feel that the problems become harder and harder. Problem 94 of Project Euler took me a good while to figure out. The problem is easy to understand and reads

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the
5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

Continue reading →

Posted by Kristian in Project Euler, 25 comments
Project Euler 91: Find the number of right angle triangles in the quadrant

Project Euler 91: Find the number of right angle triangles in the quadrant

In Problem 91 of Project Euler we are dealing with a geometry problem which reads

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
x1, y1, x2, y2  2.

Given that 0 ≤ x1, y1, x2, y2  50, how many right triangles can be formed?

Continue reading →

Posted by Kristian in Project Euler, 1 comment
Project Euler 88: Exploring minimal product-sum numbers for sets of different sizes.

Project Euler 88: Exploring minimal product-sum numbers for sets of different sizes.

Based on the number of people who have solved Problem 88 of Project Euler it seems to be a rather difficult problem. At the time of writing 2661 people have solved this problem. This post should show you that in reality the problem is not that difficult. That being said I spent the majority of a week before I got the right insights to solve it. The problem reads

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1a2, … , ak} is called a product-sum number: N = a1 + a2 + … + ak = a1 x a2 x … x ak.

For example, 6 = 1 + 2 + 3 = 1 x 2 x 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 x 2 = 2 + 2
k=3: 6 = 1 x 2 x 3 = 1 + 2 + 3
k=4: 8 = 1 x 1 x 2 x 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 x 1 x 2 x 2 x 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 x 1 x 1 x 1 x 2 x 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

Okay, that doesn’t sound too easy does it? Well I guess you wouldn’t be here if it was too easy. If you don’t want the full solution but just some insights into the maths you need to solve it, just read the first part. Continue reading →

Posted by Kristian in Project Euler, 17 comments
Project Euler 75: Find the number of different lengths of wire that can form a right angle triangle in only one way.

Project Euler 75: Find the number of different lengths of wire that can form a right angle triangle in only one way.

Assuming we have solved the problems from one end, we are now at Problem 75 of Project Euler which should unlock the 75 problem achievement as well as the Pythagorean Triplet achievement. The problem description reads

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

Note: This problem has been changed recently, please check that you are using the right parameters.

I have already noted that we should unlock the Pythagorean triplet achievement, and that is for a reason. In order to get a good solution we need to revisit the theory we used in Problem 9 about Pythagorean triples. Continue reading →

Posted by Kristian in Project Euler, 16 comments
Project Euler 71: Listing reduced proper fractions in ascending order of size.

Project Euler 71: Listing reduced proper fractions in ascending order of size.

We now have more than 70 problems under our belt and ready to attack the next one. Not that I really care about the number of problems, but this one is really really fun I think. It is easy to understand and have a really beautiful solution based on simple algebra. But lets get on with it, the problem reads

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

If we just wanted to search all the proper fractions in the search space we would have to search in the ball park of not something I am dying to do. Of course we could stop once we get about 3/7 and that would about half the search space, but still. So let’s look at another method. Continue reading →

Posted by Kristian in Project Euler, 15 comments
Project Euler 63: How many n-digit positive integers exist which are also an nth power

Project Euler 63: How many n-digit positive integers exist which are also an nth power

In project Euler‘s problem 63 we are again crawling up above 10.000 solutions, which suggests that this problem is a bit easier than the previous ones. So let’s take a look at it

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

If nothing else at least the description is short. I can ensure you that the coding we will do for this is short as well, but let us first do a bit of analysis on the problem. Continue reading →

Posted by Kristian in Project Euler, 9 comments
Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

Project Euler 57: Investigate the expansion of the continued fraction for the square root of two.

I found Problem 57 of Project Euler to be a rather interesting problem, with more than one solution. The problem description reads

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

First thing I will present is a brute force solution, which for all practical purposes are fast enough. The second solution is a closed form approximation to the problem, so it can be solved as fast as you can punch the calculator. Continue reading →

Posted by Kristian in Project Euler, 15 comments
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics

I have just finished reading Prime Obsession by John Derbyshire. A casual math book  which I will pass my thoughts and recommendations about this book in this post.


Prime Obsession is a book about the history surrounding Bernhard Riemann and the Riemann Hypothesis. A hypothesis, which is more than 150 years, and still haven’t been neither proved nor falsified. The Riemann Hypothesis tells us a lot about the Riemann zeta function and how it is linked to the distribution of  primes. This link is the turning point for the whole book.

When I first encountered the book I did not like the writing style of John Derbyshire to be honest. It was in a very conversational tone. But as I progressed through the book I partly forgot about the writing style. More importantly; the content was so great that the writing style for unimportant to me.

The book covers two aspects of the Riemann hypothesis. The even chapters (oh, the author is a mathematician after all – so why not) gives the reader a historical account about European mathematics. They cover many things from a few generations before Riemann all the way to today. I loved these chapters which introduced me to a lot of the persons naming the famous theorems that we are using today such as Gauss, Euler and of course Riemann himself.

The remaining chapters (the odd ones) covers a wide range of mathematical topics. The culmination is the explanation of the Riemann hypothesis and how the non trivial zeros of the zeta function links to the distribution of the primes. Most of the chapters were written in what I would consider being an accessible way which gives a fine introduction to the mathematical topics. It is by no means a textbook that will give you the deeper understanding of the subjects it touches, but it gives you an introduction and tells you what the idea of the subject is.

The only part I didn’t grasp was a chapter on field theory, I thought it lacked something. However, it wasn’t that essential for the main result I think. The main result was a bit complicated to understand as well, but reading the last two odd chapters again helped a lot. I wont say I understand the Riemann hypothesis in the mathematical sense, but I have a conceptual idea of what it does. So this book delivered exactly what it promised to do. Besides that it also inspired me to continue the wonderful journey through mathematics.

If you haven’t read it yet, this is an obvious choice for an item on the wish list.

Posted by Kristian in Other, 2 comments

Project Euler 42: How many triangle words does the list of common English words contain?

Problem 42 of Project Euler presents us with a new string manipulation problem. The problem asks us the following

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Continue reading →

Posted by Kristian in Project Euler, 8 comments