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.


From Novel to Movie Hell

February 16, 2010

I finished the From Hell Graphic Novel a few days ago and I’ve been reading through the appendix, which, I might add is taking me as long as reading through the main part. However, during the weekend I watched the movie again and it’s quite easy to see why Alan Moore would be so against it.

The Graphic is so strict to a lot of historical events and takes a lot of references from what appear to be reputable sources, that for a movie to be made from it would either have to take a small part of the Graphic novel or would have to be a very long movie. It’s hard to give a blow by blow account of all the failings that happen in the movie as I’m not really that motivated to sit through the movie more than twice in a lifetime. At the fore is the mixture of Mr Abberline and Mr Lees characters and the introduction of Abberline being a opium fiend. Now that I think back I don’t remember there being much mention of the letter that inspires the name of the Graphic novel.

There is also no mention of Hawksmoor’s churches which really are the main inspiration behind the Graphic novel.

Either way, just a short one, but the graphic novel is something that has inspired me to read a bit more about the ripper murders and masonry, etc.


Why can’t I delete that file?

September 2, 2009

Just a really quick post because I should be working, but I found this out just today and it’s really very useful. Whenever you get a file that you can’t delete you just want to throttle windows, or the application that’s holding the file under it’s selfish control. Well, you can find out what is holding that file with a wonderful tool called Handle.

It is a command line tool but it’s very easy to use, simply type in the following and you’ll be told (in slightly verbose terms) what has a handle to what:

handle

You will get a lot of output, but you might see something like this

——————————————————————————
EXCEL.EXE pid: 3712 TRUMPET\hba

530: File (R–) C:\Documents and Settings\hba\Desktop\Book1.xls

——————————————————————————

This tells us that Excel.exe has a handle on the Book1.xls meaning we can’t do stuff to it. You can make your life easier by using the following command to save the output from Handle so you can go back over it later (the following command saves the output to C:/handle.txt).

handle > C:\handle.txt

There you go then, that’s that, not so technical so sorry about that maybe it’ll do a more in depth one later.


Useful windows shortcuts

August 1, 2009

Im always looking for new Keyboard shortcuts and I found this rather special gem today in my rss feeds.

Quickly position two windows side by side in WinXP.

  1. Ctrl+Shift+Esc: Opens TaskManager (I didn’t know this before, very useful shortcut instead of Alt+Ctrl+Del then ‘t’)
  2. Select two or more windows that you want side by side (can use Ctrl+Space for this plus up, down).
  3. Alt+W which opens the Windows menu.
  4. V to Tile Vertically, H to Tile Horizontally.

Taken from The Old New Thing and I have a bunch of others that I use frequently.

Windows Key + E: Opens Explorer window so you can navigate your hard drives.

Windows Key + D: The first time it shows the desktop, the second time it restores the windows.

Windows Key + M: Minimizes all windows.

Windows Key + Shift + M: Same thing as the second time you press Windows Key + D, restores the minimized windows.

Windows Key + L: Locks the workstation instead of Ctrl+Alt+Del then k.

Windows Key + R: Opens the Run dialog, this can also be useful for navigating to a directory quickly.

Windows Key + Tab: Same thing as Alt+Tab but on the TaskBar, except you have to press space for that application to gain focus.

Alt+PrintScreen: Same thing as PrintScreen except it only copies the currently selected window.

So far this is really it without getting in to application specific shortcuts, hope this helps someone out there.


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.


WIRED – Wall Street Netbooks and the Music Industry

March 15, 2009

I bought a copy of Wired, the American issue a few days ago and I must say I’m really rather impressed by it. I bought it because of an article it has called The Secret Formula that destroyed Wall Street. It’s all about a formula called the Gaussian copula formula which was, as far as I can make out, used to calculate risk on different kinds of loans from the high end loans only banks deal with to, and more importantly, your regular mortgage. However, I’m really loving my latest purchase of this magazine, it’s got quite a few really interesting articles in it, including one on Watchmen that I have yet to read.

Included in the articles are an article on music games like Rock Band and how the music industry in all its wisdom is pulling support from these games because they don’t give enough in the form of licensing fees and returns. What they’re doing I see as essentially opening up the market for independent music distribution and licensing, giving more variety and freedom to those who want to get their music out there. Think about creating a tune for a game like Rock Band specifically as a band and getting it known through the console, then, when popularity has increased, or even before, sell it over iTunes or some other internet distributer.

Recently I bought a netbook, a Samsung NC10 to be precise, it’s an absolutely fabulous piece of hardware, it runs everything I could really want on the move and I can even code some Assembly on it. I write most of my blog entries on it on my way too and from work and I feel quite proud of it when I pull it out on the tube on the way too or from work. However, there is a point to this, the WIRED issue has an article on Netbooks that really makes you think about the direction the hardware industry for computers is really going. Here, is a netbook, a low cost, low powered, device that can really do anything you want to do on it. If you have an internet connection you don’t even need to worry about installing a word processor on it. There really is no real need for most people to have high performance computers when you can just sit down snug on a char in Starbucks with a netbook and get on with whatever facebooking-myspacing-shenanigans you want. For ages coders have been taking advantage of high powered pcs by coding bloatware, sloware, bulkware, etc and now you have these low powered netbooks that are what we had maybe four years ago in high end laptops and if software developers really want to stay atop of the market they’re going to have to start shaping up and coding better. That’s just my personal opinion on how bad a lot of programs are coded these days though.

Finally, we have the article on the Gaussian Copula Function which I’ll probably write an article on as well as Watchmen. At the moment I’m so impressed with WIRED US that I want to subscribe but I’m going to be waiting to see if the next issue is any good.