# Shaun Abram

Java and Technology weblog

## 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

## Hiatus

It’s been a while since I posted last. Wedding planning (7 weeks to go…) and work have been getting the better of me. I have some ideas for future posts, but until I get the wedding out of the way, things are likely to be quieter. But I will post my next Project Euler solution soon at least…

## 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...

## Find files in Unix

I frequently end up searching an entire directory for an elusive file and I can never remember the exact command structure, so posting here:

` find /dir/to/search -name "filename.ext" 2>/dev/null`

And wildcards are allowed. e.g.

` find . -name "filename.*" 2>/dev/null`

The latter command searches the current directory AND all sub directories.

The ‘2>/dev/null’ avoids those annoying “find: cannot read dir …: Permission denied” errors.

You can even simplify it by creating your own find.sh script that takes the file name as a parameter:

```
#!/bin/bash
echo "Searching for files called $1 in current dir and all sub-dirs"
find . -name "$1" 2>/dev/null
```

Meaning you just need to call, for example:

` find filename.*`

Also, if you want to search for files containing specific text, try

` find /dir/to/search -exec grep -il "txtToSearchFor" {} \;`

The “-il” means ignore case and print only the names of files with matching lines (as opposed to the line contents).

Update 4 May 2014: I have added variations of these scripts to my scripts repo on Github. Specifically findf (find files) and findt (find text in files);

See also:

- http://en.wikipedia.org/wiki/Find
- http://www.unix.com/unix-dummies-questions-answers/3152-find-files-containing-text.html
- Ignore git (or svn) directories in a find

Tags: bash, find, scripts, search, unix

## 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; i
```

Note the use of the HashSet to avoid counting duplicates (i.e. numbers divisible by 3 *and* 5, like 15, 30 etc). Obviously the code could be tidied up but this reduced the number of loop iterations from 999 to 532 (and the run time from ~110ms to ~90ms).

However, the code/algorithm is still imperfect as although it doesn't count numbers divisible by 3 *and* 5 twice, it still iterates over them twice. I couldn't figure out a way to avoid this, so having met the requirements (I verified the correct answer on the Euler site and, at ~90ms, it runs well under one second), I submitted my answer and started reading the supplied solution.

The 'perfect' solution involves 3 breakthroughs.

The first is that the ideal solution involves using formulae, not iteration.

The second is that in the example of the total all numbers up to 1000 divisible by 3

i.e.

3+6+9+ ... +999

= 3*(1+2+3+...+1000/3)

where 1000 divided by 3 is rounded down.

The 3rd and final breakthrough required is that:

1+2+3+...+y

= (y/2)*(y+1)

I have to admit that I am not sure I would have ever made these break throughs myself!

But using these facts, the ideal solution is along the following lines:

```
``````
static int max = 999;
static void main(def args) {
int total = sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)
println(" \ntotal="+total)
}
static int sumDivisibleBy(n) {
int p=max / n
return n*(p*(p+1)) / 2
}
```

This solution reduced the run time from ~90ms to ~20ms.

Next up, Problem#2...
One of the toughest tasks on a project can be coming up with estimates, so I was interested to see this blog post quoting some of Joel Spolsky‘s thoughts on creating specifications and coming up with quotes for client work, which I think makes a lot of sense. Tags: consulting It’s been a while since I have posted here; The last 2 months have been hectic. I started a new project at work (I’m “Tech Lead”, on site at a major bank here in California, using Java/XML/Spring), took a vacation in Europe, did a best man’s speech at a friends wedding, and completed the Escape From Alcatraz triathlon. Been a busy time! I have a few ideas for upcoming articles, and I am also thinking about taking the Spring Certification exam. If so, I will be sure to post about it here… There is an interesting article on TheServerSide today, about a book called “97 Things Every Software Architect Should Know”. It contains some good articles from some well known authors and architects, all short and easy to read. My personal favorites are## Spec’ing and Pricing Client Projects

## Back from Hiatus

## Things Every Software Architect Should Know

```
```

```
```