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 ?

Advertisements

Game Theory – An Introduction

March 27, 2009

Game theory, as with most logical and mathematical disciplines has interested me for a long time but until recently I haven’t had time or the motivation to look in to it very far. On my reading list from Christmas I have a small introduction to Game Theory. So far it’s been really quite interesting, I’ve lost the plot a few times and not understand one of the very basic concepts because of some of the wording, but it’s got all the information and there are no hard to understand formula.

Game Theory then, from what I understand of it so far, is the maths that can be used to determine what a ‘rational’ thing (or things) would do in a given situation. It’s applied across the board from the decisions animals and insects make and why they should make one decision over another all the way to what I should do in a game of poker.

In a basic game like Matching Pennies you can explain the very basics of Game Theory. The game involves two players, each has to choose either Heads or Tails on a penny and when they reveal their choice the first player wins if both pennies are the same (Heads, Heads/Tails, Tails) and the second player wins if the pennies are missmatched (Heads, Tails/Tails, Heads). It is known as a Zero-Sum Game because one player wins and the other player loses, i.e both players ‘payoffs’ are balanced, I win, you lose, visa versa, or a draw occurs in which all players get 0 payoff. A Zero-Sum game is therefore a game of pure-conflict, to maximize my payoff I have to try and make you lose by winning and visa versa. You could change Matching Pennies so that it was no longer Zero-Sum by giving some of the options benefit for both parties or the opposite. If we say that anything with a Tail in it means that both players win then it might be beneficial, if you know your opposition will play Heads, to always play Tails.

Game Theory is used to demonstrate what the best strategy is for both players, should the first player always go Heads, choose Heads two-thirds, one-half, one-quarter of the time, or maybe not at all? A decision matrix can be drawn up for the Matching Pennies game whereby if you win you get 1 and if you lose you get -1, that way the payoffs are balanced at a round 0.

Player 1
Heads
Player 1
Tails
Player 2
Heads
+1
-1
-1
+1
Player 2
Tails
-1
+1
+1
-1

In the top left you can see that if both player choose Heads then player one gets +1 and player two gets -1. We can understand from simple common sense that there isn’t really a best strategy unless you know what the other player is going to do, so I’m best off choosing Heads/Tails with an equal probability of 50%. This is called a mixed strategy as opposed to a pure strategy which will determine what a rational person should do in any situation of a Game.

Game Theory seems like it could be very useful in lots of situations where one should make a decision, the more I think about it the more I believe I’m going to start pondering options I take in terms of Game Theory.


Intelligent Design

April 3, 2008

Thinking about Intelligent Design I came across two realisations.

1) If God is Perfect then Intelligent Design is not possible. Fundamentally this comes down to the arguement that if God is perfect we cannot apply Human traits to God. Lets say for instance that Intelligent Design is correct, there was a creator, by saying they are intelligent it means that they had to think about and design everything. This means that they are partly human, they aren’t Perfect, therefore there is something more Perfect than they and they are not the most Perfect being. This doesn’t work for a monotheistic religion like Christianity.
I am also aware that this is a little more complicated than I have put forward, but I believe the next point will tackle the issue.

2) The way we define Intelligence is down to logic, thinking, design, perfection, etc. Therefore, for Intelligent Design to be possible we have to have a God that is logical, who can think and Design as we say it. However, if God is all knowing then he has no reason for logic, intelligence or design, so to say that we are Intelligently Designed says that we Had to be Intelligently Designed. Therefore God cannot be all knowing and so is not God.

As an aside, if God is Perfect and all knowing then he knows the future and so cannot design what he knows is going to happen. Also, it means he has no control over what is going to happen and so presumably is not Perfect. Mostly symmantic arguements and applying Human wording to a higher being, but interesting that God appears to transcend our definition of him but Christians still confine him to their definitions all the time.