Pythagorean triplet

Project Euler again, this time its problem 9.

A Pythagorean triplet is a set of three natural numbers, a<b<c, for which:

a^{2}+b^{2}=c^{2}

For example:

3^{2}+4^{2}=9+16=25=5^{2}.

There exists exactly one Pythagorean triplet for which abc = 1000.
Find the product abc.

My first draft is simply brute force checking:

Module Module1

  Sub Main()
    Dim beganAt As Date = Now

    Dim answer As Integer = pythagorean(1000)

    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds

    Console.WriteLine(answer.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub

  Private Function pythagorean(ByVal thisNumber As Integer) As Integer
    For a As Integer = 1 To thisNumber
      For b As Integer = 1 To thisNumber
        For c As Integer = 1 To thisNumber
          If a + b + c = 1000 Then
            If (a * a) + (b * b) = (c * c) Then
              Return (a * b * c)
            End If
          End If
        Next
      Next
    Next
    Return -1
  End Function

End Module

It takes 375 milliseconds but gives the correct answer.

 

The 10001st prime number

Project Euler time again, I’ve come out of sequence – here’s problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

I’m going to start at the beginning and check if each is a prime, until I find the 10001th.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n = 10001
    Dim prime As Integer = 0
    Dim counter As Integer = 0

    ' Check each number until you've got 10001 prime numbers.
    Do Until prime = n + 1
      counter = counter + 1
      If isPrime(counter) Then
        prime = prime + 1
      End If
    Loop

    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds

    Console.WriteLine(counter.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub

  Private Function isPrime(ByVal thisNumber As Integer) As Boolean
    ' Prime numbers other than two are odd...
    If thisNumber = 2 Then
      Return True
    ElseIf thisNumber Mod 2 = 0 Then
      Return False
    End If

    'Check it isn't divisible by up to its square root
    '(consider n=(root n)(root n) as factors)
    For counter As Integer = 3 To (Math.Sqrt(thisNumber)) Step 2
      If thisNumber Mod counter = 0 Then
        Return False
      End If
    Next
    Return True
  End Function

End Module

I used a function for finding primes, it keeps coming up. It takes an integer and returns true or false by discounting even numbers except 2 and checking for divisibility up to the integer’s square root. If you consider n=sqrt{n} times sqrt{n} then if you have not found a number that divides into n evenly once reaching sqrt{n}, its factors can only be one and itself. This significantly reduces processing time and appears to be how my HP40gs works out its ISPRIME() function.

It gives the answer 104743 in 125 milliseconds.

Largest prime factor of a composite number

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Prime factors are prime numbers that can be multiplied together to make a given number. One way to find them is to start by dividing the number by the first prime (2) and continuing to do so until it cannot be divided, then moving on to the next.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n As Long = 600851475143
    Dim factor As Integer = 2
    Dim highestFactor As Integer = 1
    While n > 1
      If n Mod factor = 0 Then
        highestFactor = factor
        n = n / factor
        While n Mod factor = 0
          n = n / factor
        End While
      End If
      factor = factor + 1
    End While
    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds
    Console.WriteLine(highestFactor.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub
End Module

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.

 

 

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.

Install web applications locally on Ubuntu

I was talking with someone yesterday who is hacking a WordPress theme together. If you work with web sites, being able to run a site locally allows testing, experimentation, developing new themes and even just checking that a software update isn’t going to break your site. You might want to keep a web application on a local network and away from the Internet – such as StatusNet, a Wiki or a project management application. All we need is to install a LAMP stack – Linux Apache MySQL and PHP. We’ve already got the “L”! So let’s walk through installing WordPress. Continue reading Install web applications locally on Ubuntu

Blogging platforms

Has anyone else noticed a large amount of ping backs to link farms from Planet Ubuntu feeds over the last few days? I’m getting a fair few. I’d give an example but if I link to a site that takes my posts from a syndicated site and creates posts that are syndicated on other sites I might create some sort of perpetual motion blog post and consume the Internet (it might seem far fetched but what if Robert Morris had stopped to think).

I find these objectionable though – they appear to be WordPress and I guess are using a plugin to pull feeds in and publish as articles. They’re not as bad as flat out plagiarism – which I’ve experienced. Mind you even that isn’t the worst, I once wrote a howto which was CC licensed and I realised it had been ripped off when someone posted a comment on it suggesting (quite strongly) that I had taken it from the thief!

So it occurs to me that maybe this is a WordPress thing. Then again maybe not. Like so many of us I get stuck in my ways and WordPress is like a pair of comfy shoes. Maybe I should try a new platform, so I wondered what was popular out there in Ubuntu-land.

I’ve tried Drupal (I don’t like it, sorry Emma), Serendipity and Pixie (I quite liked that but baulked at the theming system). Mind you I also have quite a lot of time to myself over the next four months, maybe I should roll my own, I’ve hacked around in PHP but have never developed a large project using it.

So let me know, suggestions on a postcard. Maybe just a comment here will suffice.