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.


KickAss

March 26, 2010

I had been meaning to read the KickAss comic for quite some time and with the release of the movie I took the jump and bought the graphic novel.

Kickass, for those who don’t know is a comic about a kid who decides to don a lycra suit and mask to fight crime. Gets the crap beaten out of him, and then the story goes on. The comic has been so popular that it has already been made in to a movie that has just been released here in the UK.

In the beginning I found it to be really engaging, the characters were my type of people, geeky, inquisitive and witty.  I, and loads of others I assume, could relate to the comic geekery, the hoarding of comics and wonder at how no one could have tried to be a super hero (which still does beg the question, how has no one done this yet?).

The story progresses quite happily for quite some time and it’s predictable but interesting and new, then, out of nowhere it falls like shit from a plane.  Although I didn’t anticipate the twist I can see it being quite easy to predict and by the end I was pretty annoyed at how it had all gone.

I’m happy to say that the setup for the sequel made me want to vomit and cry with disapointment. I want to start reading it monthly but I don’t to start paying for it, I just hope that Nemesis is a little better.


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.


From Hell

February 12, 2010

My wonderful girlfriend (I have to say that because she is and because she’s sat next to me) bought me From Hell for Christmas. It’s been something that I’ve been meaning to read for a while after borrowing it from a friend and failing to read it.

After failing to read it the first time I went into my local Comic shop, Gosh Comics (they’re awesome) and had a conversation with someone there about Alan Moore and his inability to write anything bad. It was at this point that I admitted to not finishing From Hell and was chastised for it. It was actually a little more complex than this and I came away feeling a little stupid.

Anyway, cutting to the chase, I have to say that I think From Hell is probably the best Graphic Novel I’ve read. I didn’t think I would like the artist style at first, a sort of haphazard mess of etchy lines. It really pulls you in though, from the quieter moments to the grusome hacky slashy ripper moments, it all comes together really nicely. Eddie Campbell is an exceptional artist and I have to say I’m looking forward to reading Alec a lot.

The rest is also really great, it drags you in and I think it helps that I’ve grown up and live in London. Being able to recognise parts of London in Campbell’s art and relate to all the places the murders took place. Learning about Hawksmoor’s churches and wondering how much of the whole thing is fact and how much is thought up from Alan Moore’s magnificent mind.

I’m really looking forward to reading the appendix and doing a bit of research into Hawksmoor, the murders and the masonic cut on the whole thing.


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.


Scientology – my main problem

August 2, 2009

It’s been a while since I’ve written or even thought about Scientology, but just today I read a post over on My Scientology Blog, which was actually the response to some questions asked by a reader. One line really jumped out at me when I read it and it was the following:

The tools we have in Scientology don’t require belief in order to work.

My main problem with Scientology has always been that it categorizes itself as a religion and yet claims that you do not need to believe anything to be a part of it. So, how can it be a religion when we get the definition of religion from any dictionary it always contains the aspect of belief.

Religion:

1. beliefs and worship: people’s beliefs and opinions concerning the existence, nature, and worship of a deity or deities, and divine involvement in the universe and human life

2. system: an institutionalized or personal system of beliefs and practices relating to the divine

3. personal beliefs or values: a set of strongly-held beliefs, values, and attitudes that somebody lives by

From Encarta Dictionary.

If Scientology was openly a Self-Help system, a set of products for bettering yourself, or even agreed that it’s comparable to Psychology and Psychiatry I wouldn’t have any qualm with it. The rub comes with it claiming it’s a religion, by this definition Science is a religion and so pharmaceutical companies are religious entities.

I just have to sort out a set of questions I can pose to a Scientology that will make them contradict themselves.


Follow

Get every new post delivered to your Inbox.