Sunday, September 27, 2009

On solving Project Euler - Part 2

In the previous post, we saw that some of the Project Euler challenges could be solved using naive brute-force algorithms directly transcribed from their description. Today, I would like to introduce another category of problems, which is an extension to the previous one: problems that can be easily solved using mathematical software.

Some of the Project Euler challenges target mathematical fields using very large numbers: for example factorials. As you might know, in programming languages such as C, all the built-in mathematical operations can only be performed on a limited set of numbers: int, long, etc. In order to perform operations on bigger numbers, you will have to rely on specific libraries such as GNU MP Bignum, and use a different syntax (no more "+" or "*" operators). This results in ugly code, and more trouble only to write simple algorithms.

For this category of problems, if you still want to implement naive algorithms, you should choose a programming language which naturally handles big numbers. Actually, most of the "recent" programming languages like Ruby, Clojure and Factor can handle them without you notice it.

Let's take the problem 16 as a first example:

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

One can imagine that 2 raised to the 1000th power is a very large number: indeed, it actually has 603 digits! This is far more that what standard the standard long type can handle in C: 232 -1 (4,294,967,295).
Fortunately, it is a peace of cake for Ruby to handle these numbers. As you will see in the source code below, no special syntax is required to perform operations like additions on large numbers, you can use the usual operator "+":

I would like to give a special mention to the J programming language which, apart from handling large numbers as easily as Ruby, also provides a very concise syntax when it comes to number processing, as shown in the following code (solution to the previous problem):


Another problem that can be solved easily with languages that naturally handle large number is the problem 20:

n! means n x (n - 1) x ... x 3 x 2 x 1

Find the sum of the digits in the number 100!

The pattern of this challenge being the same as the 20th, the solutions in Ruby and J are quite straightforward again:




If you give a quick look at the challenges list, you will notice that many of them involve prime numbers. More than large number handling, these prime numbers are a big reason to choose one language over another in order to solve certain problems. For example, J provides built-in functions to compute efficiently prime numbers. Of course, you could use libraries like mathn in Ruby, or implement the functions that you need in Clojure, but it would just add some more trouble, and usually the efficiency can't be compared to the native functions provided by J, although it is not always an issue. So let's test the power of J by solving the 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?

J built-in function p: returns the nth prime number, so the solution can't be more simple than:

In the same field, Mathematica is incredibly powerful too, but unfortunately it is a proprietary and quite expensive system... It also provides a built-in function to get the nth prime number, and again the following code is enough to solve the previous problem:

The problem 10 is also one of those which requires prime number computation, and can be solved using a naive brute-force algorithm:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

J provides the inverse function of p:, which is p:^:_1 (you should read it p:-1): the mathematical function called pi, which gives the number of primes less than a given number n. It can be used in the following way to solve this challenge:

Again, Mathematica provides several functions related to prime numbers, such as PrimeQ, a prime testing function, which can be used to solve the same problem in a slightly different way:

Mathematica useful functions are not limited to the field of prime numbers. The problem 65, dealing with continued fractions, is another nice example showing how good Mathematica is at solving Project Euler in a clean way. Here's the self-explained source code:

We saw in this post that the field related to the challenge can drive our choice of language to solve it in a very simple way, for example with the native and transparent support of big numbers, or with powerful built-in functions to deal with prime numbers and continued fractions.
In the next post, I would like to introduce some simple and common ways of solving problems more efficiently than naive brute-force.

No comments:

Post a Comment