This Christmas I’m going to embrace the past.
COmmon Business Oriented Language (COBOL) 85 standard was the first language I was taught. Napier University was a feeder into the banking and insurance industries in Edinburgh at the time and they had sizeable COBOL farms. It proved profitable too, as a number of students I knew went to the US to alleviate Y2K bugs in thousands of legacy applications. COBOL had fallen out of favour in US colleges.
Haven’t done much Project Euler recently – I’ve been busy studying. So here is an answer to problem eight which asks:
Find the greatest product of five consecutive digits in the 1000-digit number.
First TMA on MT264 (Designing applications with Visual Basic) got returned today – 96%. I’m very pleased with that and exceptionally lucky given that I read the material in a week, attended one on-line tutorial and wrote the assessment in a couple of days.
I’ve seen complaints on the module forum that tutors aren’t getting assessments back to quickly enough. The cut off was the 15th (I submitted on the 13th) and it was returned on the 27th, I don’t really see what the problem is.
Nested selection reared its head again but I didn’t lose any marks for it. In every programming module I’ve been picked up for using Else If so I played it safe and used nested If statements. So I was advised to use Else If proving I can’t win!
Well that was emotional, the TU100 forums opened yesterday. My poor co-moderator Nicky got thrown in to the deep end (I was at a mess top table).
I checked in before work, and there were a few posts (about two dozen) so I thought we’d be OK. Checked in earlier and there’s several hundred!
I’m studying for MS221 and MT264 but it’s clear I’m going to have to put some time in this weekend reading through TU100′s material – especially with Sense, which seems to have captured student’s imaginations.
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
Seemed pretty straight forward, loop through all numbers up to 2,000,000 – if they’re prime add them to a tally.
Module Module1
Sub Main()
Dim beganAt As Date = Now
Dim n As Integer = 2000000
Dim total As Long = 0
For counter As Integer = 2 To n
If isPrime(counter) = True 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()
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
Just needed to be careful with data types – VB.Net’s Integer isn’t large enough so I changed to a Long. Gives 142,913,828,922 in 953 milliseconds.
Project Euler again, this time its problem 9.
A Pythagorean triplet is a set of three natural numbers, a
b
For example:
.
There exists exactly one Pythagorean triplet for which a + b + c = 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.
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 
It gives the answer 104743 in 125 milliseconds.
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
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, 
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.
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.