Euler – Problem 2

April 1, 2010

It’s been a couple of days since I finished Problem 1 of Project Euler and I did in fact finish Problem 2 the very next day. Unfortuantely, I must admit that I have been making some very basic maths quite complicated in the hopes of understanding how some people have solved Problem 2.

Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

At first this seems like an insurmountable task because four million is quite a large number and common sense leads us to believe that there will be hundreds of numbers in the Fibonacci sequence below four million. Fortunately this is a paradox as there are only a mear 33 numbers below four million in the Fibonacci sequence.

I spent quite some time looking for a formulae that would let me work out all the even numbers in the fibonacci sequence (i.e. even numbers are always three terms apart, so F(3n) is always an even number). Not being a mathematician and not having done any kind of maths for several years I gave up (I also do not have that much time on my hands) and found a list of Fibonacci numbers and used a calculator to add up all the numbers below four million.

After getting the correct answer I did however look in to other peoples solutions, and there are some quite facinating solutions indeed. It’s made me learn about the Golden Ratio and how it links to the Fibonacci sequence, though I have not delved too far, see previous comment about not being a mathematician.

I’m going to very briefly go over one of the properties of the Fibonacci sequence and how it can be used to find the answer to this problem.

Golden Ratio

Something can be said to have the Golden Ratio if the ratio between two things is the same as the ratio between the larger of the two things and the sumation of the two things. Given that B is greater than A, B and A are in the Golden Ratio when:

A:B = B:(A+B)

This is also known as Φ (phi) and is the irrational (cannot be expressed as a proper fraction) number 1.6180339887…

Fibonacci Sequence
This links to the Fibonacci sequence because the ratio between two consecutive terms in the Fibonacci sequence is close to the Golden Ratio (it is more complicated than this, but for our purposes this is all we need to know). I’m going to express Fibonacci numbers as Fib(n) where n is the term, so F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2… F(10) = 55.

The nth term of the Fibonacci sequence can be expressed as so:

Fib(n) = Fib(n-1) + Fib(n-2)

And so the Ratio between two consecutive terms n and n-1 is as phi.

Fib(n)/Fib(n-1) = Φ

Eventually we want the ratio between three terms, because we know that even numbers are three terms apart.

Fib(n)/Fib(n-3) = ?

We can immediately infer that the ratio is going to be 3Φ because we know that the ratio between any Fibonacci number is going to be Φ, but for sake of argument I’ll show you what took me so long to work my head around. The ratio between three Fibonacci numbers is given by the following:

  1. Fib(n)/Fib(n-2)
  2. ( Fib(n) / (Fib(n-1) ) / ( Fib(n-2) / Fib(n-1) )

Now this is the point where I got confused, how can the first part be transformed into the second part? I tried many different ways, thinking it was a ratio of ratios, or an inverse ratio of the ratio or some crazy things like that and finally someone on the irc channel #maths helped me out with the simple answer of “that’s how fractions work”. If you Divide top and bottom by Fib(n-1) then you get part 2. The use of this is because we know that Fib(n)/Fib(n-1) is Φ, and because Fib(n-2)/Fib(n-1) is basically the inverse of Fib(n)/Fib(n-1) it is 1/Φ. This gives us the last two steps which are a replacement

  1. (Φ)/(1/Φ) : Replace Fib(n)/Fib(n-1) and Fib(n-2/Fib(n-1) with Φ and 1/Φ respectively
  2. 2Φ : x/(1/Φ) can also be written as x * Φ.

Finally, we want to know what Fib(n)/Fib(n-3) is, which can also be written like this:

( Fib(n) / Fib(n-2) )/ ( Fib(n-3) / Fib(n-2) )

  1. 2Φ / (1 / Φ) : Fib(n) / Fib(n-2) = 2Φ (From earlier) and Fib(n-3) / Fib(n-2) is 1/Φ (From earlier).
  2. 3Φ : As earlier, x/(1/Φ) = x*Φ.

And we’re done, we now know that even Fibonacci numbers are a ratio of 3Φ apart and use a calculator to work out the sum of all the even terms under four million.

There is one other solution that I don’t really understand that I might put some work into understanding, but I will have to see how much time I have, before that…

Problem 3:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


Euler: Problem 1

March 30, 2010

In a vain attempt to become productive and cultivate motivation and some kind of order into my otherwist Street Fighter 4 driven life I’m attempting to get all of the Project Euler puzzles done and to write a little bit about my solution and writing a better solution. In some, probably most, cases, I will also have to go through some theory of how I got to the solution.

The first puzzle has to do with finding the sum of a series of natural numbers. It’s very close to a question that I’ve added to our list of interview questions recently labelled FizzBuzz.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

If you know how to program, or program on a regular basis the answer to this is quite straight forward and has the following steps.

  1. For each number, starting at 1 and ending with 100
  2. If the number divided by three has zero remainder output Fizz
    • If the number divided by five ALSO has a zero remainder output Buzz
  3. If the number divided by five has zero remainder output Buzz
  4. Otherwise, output the number

What we can do here, is replace the outputting of Fizz and Buzz with a summation of that number giving us the following, simpler pseudo code or flow.

  1. For each number, starting at 1 and ending with 100
  2. If the number divided by three has zero remainder, add it to the ‘output’.
  3. OR If the number divided by five has zero remainder, add it to the ‘output’.
  4. Otherwise, do nothing.
  5. After we reach 100, print ‘output’

The more important thing about this is that we recognise the OR, a number that has a remainder of zero when divided by both five and three must not be added to the output twice.

The actual Project Euler first question is as follows:

Find the sum of all the multiples of 3 or 5 below 1000.

To solve this with a programming language it is beneficial to know about modulo arithmetic and the modulo operator, but I don’t have time to go in to this at the moment.

In future I hope to go in to other peoples solutions and how optimization is brought into Project Euler.


Game Theory – The Prisoner’s Dilemma and Golden Balls

May 14, 2009

It’s hard to come in contact with Game Theory without coming across The Prisoner’s Dilemma which is a non-zero-sum game played between two people who are seemingly pitted against eachother. The following is the form in which I was introduced to The Prisoner’s Dilemma recently:

Alice and Bob are gangsters in the Chicago of the 1920s. The District Attorney knows that they are guilty of a major crime, but is unable to convict either unless one of them confesses. He orders their arrest, and seperately offers each the following deal:

  1. If you confess and your accomplice fails to confess, then you go free.
  2. If you fail to confess but your accomplice confesses, then you will be convicted and sentence to the maximum term in jail.
  3. If you both confess, then you will both be convicted, but the maximum sentence will not be imposted.
  4. If neither confesses, you will both be framed on a tax evasion charge for which a conviction is certain (but the sentence is not great).

There are then two possibilities for each gangster, either to cooperate with the other gangster, or to betray the other gangster. This for quite some time confused me as I wasn’t sure if cooperate was to cooperate with the police, or to cooperate with the other gangster. We can now build the following matrix for The Prisoner’s Dilemma.

Coop Betray
Coop
Short
Short
Free
Max
Betray
Max
Free
Long
Long

I’ve used the terms ‘Free’, ‘Short’, ‘Long’ and ‘Max’ to give you an idea of the length of time they will stay in jail for, the only one that needs explanation, I would hope, is ‘Free’ which means they spend no time in jail at all and only occurs if they Betray (Confess) and the other party Cooperates (Stays quiet).

The Dominant Strategies are marked in bold and contrary to what we would like to think, the rational solution is always to betray humanity even though you’d both get a shorter sentence if you both cooperated. This is because if I know you’re going to Cooperate I should always Betray you, that way I get off free, it is my best strategy. It must be noted that this is based on a one off game where we will never meet again and probably have never met in the first place, it makes it more interesting if you change things to say that both parties know eachother and therefore have a reason to cooperate.

I won’t go in to the specifics as I want to talk about Golden Balls which is very interesting, but you can make both players of The Prisoner’s Dilemma have cooperation as their dominant strategy by repeating the game indefinatley. This way if I betray you this time I know you’ll betray me next time and we’ll both just end up betraying each other, so, to save this happening, we both cooperate forever.

After looking in to The Prisoner’s Dilemma a bit more I discovered what most people call a real-world example of The Prisoner’s Dilemma in the final round of a gameshow called Golden Balls. This was a TV game-show that aired on ITV in the United Kingdom in 2007 and was hosted by a comedian called Jasper Carrot. The main workings of the game are unimportant, what matters here is the final round. Each contestant, of which there are two, chooses a ball, either Split, which means they try and split the money or Steal which means they try and steal the money. There are three outcomes as follows:

  1. Both players choose Split:- The winnings are split equally between them.
  2. One player chooses Steal, the other Split:- The player who Stole gets all the money.
  3. Both players choose Steal:- No-one gets any money.

To compare it to The Prisoner’s Dilemma, (1) is the same as both gangsters cooperating and getting a short sentence, (2) is the same as one gangster choosing to betray the other and the other gangster cooperating and (3) is the same as both gangsters betraying eachother and both getting a long sentence. From this we can build a simple table that gives payoffs of 100% for winning all the money, 50% if they split the money and 0% if they don’t get anything.

Split
(coop)
Steal
(betray)
Split
(coop)
50%
50%
100%
0%
Steal
(betray)
0%
100%
0%
0%

The problem is the same as The Prisoner’s Dilemma except it is not quite as pure. This is a one time thing, but the players are in the same room, in fact, they’re looking right at each other, their friends and family are watching and they are given the opportunity to convince the other person of their intention to either Split or Steal. There is more at stake than some money, their reputation amongst all people for one. On top of all of this they have been playing a game for the past half hour and have had the chance to betray eachother already, this is not now a case of a pure game, this is now a case of a sub-game.

The best and most amusing example of this follows in this youtube video. I think, more than anything, this video explains The Prisoner’s Dilemma and why it’s a dilemma and causes so much pain and heartache for so many economists, philosophers, psychologists and humanitarians around the world.