Sum of all even Fibonacci terms below 4 million

The second Euler problem concerns the Fibonacci sequence, which for anyone doing MS221 is the basis of module A1.

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Following the logic from the previous problem, then I can check each number of the Fibonacci sequence to see if it’s even and add it to the total, n_{3} = n_{2} + n_{1} where n_{0}=1. We need to repeat this while n < 4000000 and add n to our total if it’s even.

Sub Main()
    Dim beganAt As Date = Now
    Dim n, n1, n2, total As Integer
    n1 = 0
    n2 = 1
    Do While n2 < 4000000
        n = n1 + n2
        n1 = n2
        n2 = n
        If n < 4000000 Then
            If n Mod 2 = 0 Then
                total = total + n
            End If
        End If
    Loop
    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds
    Console.WriteLine(total.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
End Sub

Gives an answer of 4613732, which is correct. I know there is a more efficient approach but I’m tired and pissed off. Today was not a good day.

 

 

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

Project Euler’s first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

By brute force I can write code that checks every number below 1000 to see if it’s divisible by 3 or 5, if it is then add it to a running total.

I’m using Visual Basic (VB.Net 2010 to be precise). This might seem a little odd for an Ubuntu member but I’m thinking of trying MT264 (Designing applications with Visual Basic). Open University students qualify for Microsoft’s Dreamspark promotion, so I got a copy of Visual Studio 2010 Express to try it out. Besides, I’m at work so haven’t much choice.

Starting off with a “Console Application” template:

Dim beganAt As Date = Now
Dim total As Long = 0
' Repeat a thousand times
For counter As Integer = 1 To 999 Step 1
     ' Check if the current integer is divisible by 3 or 5 and
     ' if it is then add it to our total
     If (counter Mod 3 = 0) Or (counter Mod 5 = 0) Then
          total = total + counter
     End If
Next
Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
Dim took As Integer = endAt.Milliseconds
Console.WriteLine(total.ToString + " in " + took.ToString + "ms.")
Console.ReadKey()

Running this code and clicking the button we get the answer 233168, which Project Eular confirms. Code must run in less than a minute, the timer shows less than a millisecond.

I can see another way to do this, by using two for loops – one in steps of 3 and one in steps of 5, adding the counter to a total for each. I don’t know if this offers a significant time saving, so I re-ran the original code, making the loop repeat a million times and it completes in 375ms. I can’t see any value in going any further.

Finally succeeding?

I read an article by James Somers at The Atlantic called “How I Failed, Failed, and Finally Succeeded at Learning How to Code“. I’d encourage anyone with an interest in learning to code to read it – he discusses how computer programming is an excellent learning experience but that his own experiences have been tempered by poor instruction, particularly from books. He goes on to discuss how Project Euler became the titular success.

Euler provides a series of programming challenges of increasing difficulty, as the student solves each in turn they gain experience of what does and does not work as well as confidence in their abilities. Importantly, the student is also applying programming to practical problems (if you’re a mathematics student) from the outset.

I’ll post my solutions here as I go. I’m aiming to do one a day but I’ll see how I get on. Not sure what language is best to get on with, Python is popular in open source circles but most of my courses are based around Java.

 

Twitter vulnerabilities, using Windows, studying and new WordPress themes.

Graham Cluley, a Senior Technology Consultant at Sophos, has a nice blog piece on the Twitter worm from earlier this week. To cut a long story short, he reminds us of the importance of sanitizing inputs.

Still, it was more productive than my week with my Open University module that starts in October – T175 (Networked living: exploring information and communication technologies). The OU can be very Windows dependent but this course seems to be pretty much delivered in Virtual Learning Environment (what the OU calls Moodle). I ran the course DVD, which is a Windows Flash standalone thing which got me to revive the OU Ubuntu Users group, sending out emails, starting a mailing list and trying to get things going again.

So why was it unproductive? Well, I haven’t booted Windows in ages – there were a million updates, one of which was for the wireless driver. Update completely borked the wireless and I wound up restoring the drive. That aside, one thing I really like about Ubuntu (and most distributions) is a centralised update manager – Windows has Adobe, Java, Windows Update, Firefox and McAfee all trying to pull updates at the same time. It makes the system completely unusable for the first ten minutes it’s on!

Any way, I decided to build a new WordPress theme. Same colour scheme, more rounded edges – should be available in the next few days.