Shaun Abram
Technology and Leadership Blog
Subscribe to RSS FeedProject Euler: Problem 3 in Ruby
Problem 3 in Project Euler is as follows:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I had previously solved this in Groovy/Java. Here is my Ruby solution…
Read my solution below
Project Euler: Problem 2 in Ruby
Problem 2 in Project Euler is as follows:
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.
I had previously solved this in Groovy/Java. Here is my Ruby solution…
Read my solution below
Project Euler: Problem 1 in Ruby
In the process of trying to enhance my Ruby Skills, I am revisiting some of the Project Euler problems. I previously did problem 1 in Groovy/Java. Here is my Ruby solution.
Read my solution below
Project Euler: Problem 6 (in Java)
Problem 6 in Project Euler is as follows:
The sum of the squares of the first ten natural numbers is,
1^(2) + 2^(2) + … + 10^(2) = 385The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)^(2) = 55^(2) = 3025Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Tags: euler
Project Euler: Problem 5 (in Java)
Problem 5 in Project Euler is as follows:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
Tags: euler
Project Euler: Problem 4 (in Groovy)
Problem 4 in Project Euler is as follows:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
I found this problem significantly easier than problem 3, thankfully.
My first step was to write a helper method:
boolean isPalindrome(int num)
My first attempt was, as usual, the brute force approach. Namely, go through every number from 100 to 999 and for each, multiply it by every number between 100 and 999. Check if the result of each of the roughly one million calculations is a palindrome – and store it if it is the biggest one yet.
My next approach was better and involved starting from the top (999 to 100) instead of the other way round. This means we can check if the largest palindrome we could possible find is smaller than what we have already found, thereby avoiding a large number of useless calculations.
This gave me a solution that runs in approx 500ms on my local PC.
Here is my final solution:
int largestPalindrome = 0;
for (i in 999..100) {
if ( (i*i) < largestPalindrome) {
//the largest possible number we can now find (i*i)
//is smaller than the biggest palindrome already found
break;
}
for (j in i..100) {
int candidate = i*j;
if ( candidate < largestPalindrome) {
//largest number we can now find in this inner loop
//is smaller than the biggest palindrome already found
break;
}
if (isPalindrome(candidate)) {
if (candidate>largestPalindrome) {
largestPalindrome = candidate;
break;//no point checking smaller numbers of j
}
}
}
}
println("largestPalindrome);
And finally, my isPalindrome method:
public static boolean isPalindrome(Integer num) {
boolean isPalindrome=true;
char[] numChars = num.toString().toCharArray();
int endPoint = numChars.length() - 1;
int midPoint = numChars.length() / 2;
for (i in 0..midPoint) {
char a = numChars[i];
char b = numChars[endPoint-i];
if (a != b) {
isPalindrome=false;
break;
}
}
return isPalindrome;
}
Project Euler: Problem 3
Problem 3 in Project Euler is as follows:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I noticed some performance issues with Groovy when I was working on this solution. I will blog about my findings later (Update: see here), suffice to say I am switching to straight Java for this solution.
After experimenting with a brute force approach, I finally came up with this solution. It is not the most elegant, but it works (in <100ms).
long x = 600851475143L;
long max = x / 2;
long factor = x;
long lastFactor = x;
for (long i=2; i= lastFactor-1) {
for (long j=factor; j>2; j--) {
i++;
remainder = x % j;
if (remainder == 0) {
if (eule3.isPrime(j)) {
printAndExit(j);
}
}
}
}
}
There are 2 main parts to the solution. The first loop starts at x/2 (since no factor of x can be greater than x/2). Basically we are checking if x/2 (rounded) is a factor of x. Then 3, then 4 etc. And when we find a number that is a factor, we check if it is prime (if so, we stop obviously). So, for example, we check if 50, 33, 25 are factors of x.
This approach works great, until a certain point, which is when we switch into the second loop. Basically, it becomes more inefficient to start checking if sequential numbers are factors of x.
Again, not the most efficient algorithm, or very well explained! But I have spent enough time on this one.
On to Problem 4…
Tags: euler
Project Euler, Problem 2 (in Groovy/Java)
Problem 2 in Project Euler is as follows:
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.
I found it fairly easy to code a basic solution to this problem:
def fibSeries = [0,1]
int sumOfEvenNums = 0
int i = 0
while (fibSeries[i]<=4000000) {
i = fibSeries.size
fibSeries[i] = fibSeries[i-1]+fibSeries[i-2]
if (fibSeries[i]%2==0) {
sumOfEvenNums+=fibSeries[i]
}
}
println("Total = " + sumOfEvenNums)
This ran relatively quickly (~100ms), so I submitted my answer on projecteuler.net and it was confirmed as correct.
With heinsight, I realise that it is unnecessary for me to store the entire sequence of numbers (in fibSeries). I just need to store 3 numbers: the latest and the previous 2.
After checking the solution notes, there is of course a more 'perfect' solution. Reaching it involves making 2 breakthroughs, which I admit I didn't make on my own!
Breakthrough 1
The first breakthrough is to see the pattern (how could I have missed it!) that only every 3rd number is even, meaning we can safely ignore the rest. The provided solution says that this is easy to prove (I have no idea how to - perhaps a step for another day). But assuming this to be true, the code can be rewritten to
int a,b,c
b = 1 //1st seed value
c = 1 //2nd seed value
int sumOfEvenNums = 0
while (c<=4000000) {
a=b+c
b=c+a
c=a+b
sumOfEvenNums+=a
}
println("Total = " + sumOfEvenNums)
Breakthrough 2
The second, and waaay more difficult breakthrough is to spot (and prove!) that there is a pattern in the even numbers. If you look at them,
2, 8, 34, 144, 610, ...
They obey following recursive relation:
E(n)=4*E(n-1)+E(n-2).
e.g. 144=4(34) + 8
and 34 = 4(8) + 2
It can be proved that for the Fibonacci numbers, the formula F(n)=4*F(n-3)+F(n-6) holds true (I even managed to get the proof of this myself, after a little prodding).
So, this leaves the following 'ultimate' solution:
int a = 0
int b = 8 //1st seed value
int c = 2 //2nd seed value
int sumOfEvenNums = b+c
while (true) {
a=(4*b)+c
if (a>4000000) break
sumOfEvenNums+=a
c=b
b=a
}
println("Total = " + sumOfEvenNums)
I am sure this could even be rewritten in a more elegant form. Especially if Groovy supported a do..while loop.
Anyway, on to Problem#3...
Project Euler, Problem 1 (in Groovy/Java)
I have been wanting to get up to speed with Groovy for while but hadn’t really found a good excuse. So when I came across Project Euler, I decided to try to solve the problems using Groovy.
I managed to solve Problem#1 today.
Note that I would describe the solutions below as being in Groovy/Java because I still fall back on my old Java habits rather than using all the Groovy language constructs available to me. Anyway…
The problem is:
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.
Unsurprisingly, I took the brute force approach first:
int n = 999, total=0;
for (int i in 1..n) {
if ( (i%3==0) || (i%5==0) ) {
total=total+i;
}
}
println("Total=" + total)
A good first start, but far from perfect as it loops through every number between 1 and n. I could improve it slightly by tweaking the start and end points (e.g. starting at 3), but it would still roughly involve n iterations.
My second attempt was this:
int n = 999, total=0;
Set nums = new HashSet();
for (int i=3; iProblem#2...