Stefano Ricciardi

Continuing with my journey learning F# I have tackled Project Euler problem number 3, which asks:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143

This problem deals with the fascinating problem of prime numbers factorization, which is considered a hard problem. So hard that our current cryptography schemes rely on this property.

This is my solution:

#light
open System.Numerics

let is_prime (x:BigInteger) =
    let rec check i =
        i > x / 2I || (x % i <> 0I && check (i + 1I))
    check 2I                 

let max_factor (n:BigInteger) =
    let factors = seq {
        let limit = float n |> sqrt |> int
        for i in 2I .. BigInteger(limit)  do
            if n % i = 0I && is_prime i then yield i }
    Seq.max factors

A few comments:

• The first function (is_prime) is a simple trial division to determine whether a given number is prime. There are cleverer algorithms to find prime numbers: see for example here For an interesting discussion you can also have a look at The Genuine Sieve of Erathostenes by Melissa O’Neill.
• The second function uses comprehension to create the list of primes which are factors for the input value. It can be demonstrated that it is enough to stop trial search at the square root of the number to be factorized. At the end we simply return the biggest factor.

This code ran in about a second on my somewhat old 2005 desktop. It’s far from perfect, but it does the trick.

In my journey to learn F#, I have recently discovered the Project Euler site, which is a wonderful collection of small algorithmic problems which you can solve in your favorite programming language.

This is the kind of excercise I needed to get my feet wet with F# after reading about it. So I started with the first two problems listed on the site.

They both deal with sequence of numbers. Having a procedural/object-oriented mindset, I have scratched my head a few times in order to find a declarative solution true to the spirit of a functional program. Everything has become clearer after I’ve dug some more into the F# Sequences.

Problem 1

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.

This is my solution to it:

# light
let test = 1
    |> Seq.unfold (fun x -> Some(x, x+1))
    |> Seq.takeWhile (fun x -> x < 1000)
    |> Seq.filter ( fun x -> x % 3 = 0 || x % 5 = 0)
    |> Seq.sum;;

Problem 2

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.

Follows my solution:

# light
let fibonacci_sequence = Seq.unfold (fun (a, b) -> Some(a, (b, a+b))) (0,1)
    |> Seq.takeWhile(fun x -> x <= 400000)
    |> Seq.filter(fun x -> x % 2 = 0)
    |> Seq.sum

A few comments:

• Here I am using the filter method defined on sequences to stop
  the sequence itself at 4 million, therefore I can get by with plain integers. Normally you would want to use BigIntegers for sequences where you’d expect to need handling large numbers.
• One of my first attempts to this problem did not have the Seq.filter part. I only had the takeWhile like the following:

Seq.takeWhile(fun x -> x % 2 = 0 && x <= 400000)

Unfortunately, this does not work since the takeWhile will interrupt the sequence as soon as it satisfies the first condition (x % 2 = 0); in other words, it yields a sequence consisting only of the value 0, which looked somehow counterintuitive to me at first.

If you are also taking your first steps with F#, you might want to have a look to the best resources to learn it.