Monday 12 January 2009

Project Euler, Problems 4, 15 and 35

Do I have a life? Apparently not... Over the weekend and then this morning I spent some time working on some more problems with Project Euler. Saturday and Sunday were pretty quiet days all in all I suppose, and am still waiting to hear about a new work project. May as well spend the time learning a bit of C++ and keeping my mind active.

Problem 4
Find the largest palindromic number that results from multiplying two 3-digit numbers together. This was quite straightforward; iterating for the two 3-digit factors it just meant I had to write a couple of very short scripts that could recognise palindromic numbers. This meant making two slightly different routines, one for 5-digit numbers and one for 6-digit numbers.
After that it was just making sure that the largest number was carried out as a result.

Problem 15
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20×20 grid? There's a picture here to show what the routes are through the 2x2 grid if you can't picture what the question means. This didn't require a program, just a little thought back to some combinatorics that I did at uni. The numbers were pretty big, too big for the computer's calculator at first; a bit of pencil and paper cancelling of factors got me there soon enough.

Problem 35
How many circular primes are there below one million? Go here to see what is meant by the term circular prime. This took a little time to arrive at an algorithmic solution. I started off by thinking in terms of the restrictions that are placed on a number if it is a circular prime. Once we move out of single digits the only digits that can be in a number are 1, 3, 7 and 9, which limits greatly the number of numbers that we would have to consider.

However, my understanding of how to permute things in C++ is not quite there yet (I could do it with no problem in Maple). In the end I went with a brute force approach: tell the program to consider the number and the circular numbers that result. Then if all of these are prime then add 1 to the total.

Inelegant if I'm honest, but it did the job.

This now takes the total to twelve! Am slightly amazed by how many I've done since the New Year. Here's hoping that I am picking up enough C++ basics for when I start to work on harder projects. Thirteen to go...

4 comments:

Anonymous said...

I still haven't figured out how to get the mum, the dad, the two girls, the two boys, the cop, and the prisoner over to the other side of the river.

NathanRyder said...

My open source Excel program wouldn't open that thing, so I didn't get to experiment with it. I've seen it before, but I never figured it out, sorry! It's definitely a tricky one I think, although I know qutie a few of my friends in the maths department at uni figured it out.

Anonymous said...

Most of the Project Euler problems don't really catch my interest: they're very computational and/or combinatorial in nature. I simply prefer the more abstract areas of math.

NathanRyder said...

Ah, you see I like the way that many of the problems require you to do a lot of thinking before you put an algorithm together.

I need to find some good number theory problems to think about though, keep my mind working on some "proper" maths! ;)