Project Euler again, this time Python. The problem is to sort a list of 5000 names alphabetically then give them a value. For example “COLIN” is 3 + 15 + 12 + 9 + 14 = 53 and is the 938th item – so its value is 49714 (53*938).
Project Euler problem 21 is to find the sum of all amicable numbers under 10000. An amicable number is:
Let be the sum of proper divisors of then and if then and are amicable numbers.
OK so today I’m trying problem 12 – find the first triangular number with over 500 divisors. This is the first Project Euler problem I’ve really struggled to find a solution in a reasonable amount of time. Continue reading “First triangular number with 500 divisors”
I needed wxMaxima but the version in the repositories is a little older (one major revision). Compiling from source is straightforward but a recent discussion I had with students showed they shied away from it.
So I figured I’d try packaging and a couple of hours later and I’ve a copy in my PPA. I’m unsure who maintains the packaging guide so I wanted to say thank you on Ubuntu Planet hoping those involved see it. Its great when you want to try something, find comprehensive instructions and can wrap it up in a few hours.
I bought a new laptop the other week, a Samsung NP-RV511-S02UK. I have been using a Samsung NC10 dual booting Ubuntu and XP. An NC10 is a wondrous thing but when push comes to shove, a 1280×600 resolution is too small for Visual Studio work – especially when you want to see a PDF at the same time.
I’ve been reading over the course material for MS221 (I quit this module’s last presentation for personal reasons).
Khan Academy has a very good series of videos. Plus it gives you points (seriously I’m addicted to rewards – you should see me driving for PS3 trophies).
Anyway, for block A part 1 try these: Introduction to Geometric Sequences, Sequences and Series (part 1 and part 2) and Write a Fibonacci Function; for part 2 try Introduction to Conic Sections through to Foci of a Hyperbola and Parabola Focus and Directrix.
Project Euler again, this time its problem 9.
A Pythagorean triplet is a set of three natural numbers, abc, for which:
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 then if you have not found a number that divides into evenly once reaching , 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.
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