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.


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.


Firefox ‘feature’ strikes again

September 17, 2008

We all remember, well, I remember, when Firefox had a wonderful feature that hogged memory like nobodies business. This was to do with the way it cached tabbed browsing and there was, I believe a way to turn it off.

I use firefox for certain sites that I can’t access any other way (continuum, which has a bug in its cookies that Firefox apparently doesn’t handle properly) and I’m ok with it, it does what it’s mean to do (for me), for the most part. However, today I came across this bug which is a problem with the way that Firefox’s anti-phishing works. It basically states that if a file path is being sent to the server through a form it should be truncated so that just the filename is sent and not the full path. What a great feature, all those forms I’m going to fill out with full paths which could be used by phishers (there probably is a usecase), but the real problem comes when you have someone like this guy who clearly needs the standard functionality.

Once again Firefox team haven’t really thought through their ‘feature’ and it’s going to cause them problems with Chrome and Opera being strong contenders. Opera having all the functionality and more of Firefox (without the ability to write complex extensions) and Chrome being the new kid on the block with a whole host of its own problems but the ability to move forward in a way that Firefox doesn’t seem to be able to.