[2009.03.01] The Sieve of Eratosthenes in F#

There are a number of Project Euler problems that involve prime numbers. I figured that before tackling those, I better learn how to generate prime numbers. As such, I have looked at the classic approach, called The Sieve of Eratosthenes. I did not follow that algorithm exactly as described on Wikipedia, but the solution is the same. The listing below shows how to use the code.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 // The Sieve of Eratosthenes

    5 // You can get more information on the algorithm

    6 //  by searching http://en.wikipedia.org

    7 // I did not follow the exact method outlined, but

    8 //  the results are the same

    9 // My method removes odd and even numbers from the

   10 //  list in one go, and the remaining will be

   11 //  primes

   12 let rec sieveOfEra xs =

   13     match xs with

   14     | [] -> [] // if empty list passed in, quit

   15     | h::t ->

   16         h::(sieveOfEra

   17            (List.filter (fun x -> x % h <> 0) t))

   18 

   19 // Example:

   20 sieveOfEra [2..100]

   21  > val it : int list

   22 = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37;

   23     41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83;

   24     89; 97]

Actually, it too me a little bit to get the answer, in terms of programming. I had the recursion returning int -> list -> list instead of just int -> list. That is because in the match section, I was recursing the wrong data structure. Initially I had something like:

| h::t -> h::(List.filter

    (fun x -> x % h <> 0) t) sieveOfEra t

The best part is I figured out what I was doing wrong, just before I fell asleep this morning :-)

[2009.02.23] Project Euler: Problem 4

Project Euler in F#!

Project Euler: Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.

Example

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Solution

I seriously don't like how I came about with this solution and I think to myself that it is the worst of them out there. I suppose not knowing every single operator or trick in F# results in coding like this.

The idea behind this was that once I found a product, I needed to test if it was a palindrome. I even thought about trying out regular expressions but I felt more comfortable with this approach although it is a bit more verbose than I had hoped for. So I converted each product to a string and further broke the String down to a character array since I could then use the Array.rev function to reverse the members of an array.

So the formula here is to calculate the produce, convert it to a string, get the reverse of the string and compare the two for equality. Note that F# has built in support for reverse for loops using the downto keyword. Also, the problem asked specifically for 3-digit computations, so I figured out that the best best was the try all products in the range of 900-999 first, then go lower if need be.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 // function to reverse a string

    5 let reverseString (num: int) =

    6     // convert to a string, then to char array,

    7     //  then call Array.rev

    8     let charArray =

    9         Array.rev ((num.ToString()).ToCharArray())

   10     let mutable str = ""

   11     // loop through each character in

   12     //  the char array and add each to an

   13     //  empty string

   14     for i = 0 to charArray.Length - 1 do

   15         let value = string charArray.[i]

   16         str <- str + value

   17     str // return reversed string

   18 

   19 let palindrome (p: int) =

   20     // create emtpty string to hold results

   21     let mutable res = "" 

   22     for i = p downto 900 do

   23         for j = p downto 900 do

   24             let num = i * j

   25             let numToStr = num.ToString()

   26             let revString = reverseString num

   27             if (revString = numToStr) then

   28                 printfn "------%d, %d" i j

   29                 res <- numToStr 

   30     res // this will not return the correct result

   31     // need to use the command window and get the

   32     // first i,j pair

   33 // the result is: 993 * 913 = 906609

[2009.02.22] Project Euler: Problem 6

Project Euler in F#!

Project Euler: Problem 6

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Example

The sum of the squares of the first ten natural numbers is:
1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is:
(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Solution

This is a pretty simple problem, especially in F#. Yes, I know it can be reduced to one line, but I did it this way to increase readability at least. In addition, I tried to use lazy sequence evaluation instead of lists.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 let sumOfSquare =

    5     seq{ for i in 1 .. 100 -> i * i }

    6     |> Seq.fold (+) 0

    7 let squareOfSum =

    8     seq{ 1 .. 100 }

    9     |> Seq.fold (+) 0 |> (fun x -> x*x)

   10 let result = squareOfSum - sumOfSquare

   11 // result = 25164150

[2009.02.22] Project Euler: Problem 2

Now that my previous WPF project is done, I can get back to some F#! Again, I am using Project Euler as my demo platform.

Project Euler: 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.

Example

Given the first 10 terms, the sum of the even valued terms will be:
2 + 8 + 34 = 44

Solution

This problem is divided into two parts: creating the Fibonacci sequence and then summing up the even valued terms. The listing illustrates the solution.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 // create recursive function to

    5 //  generate Fibonacci sequence

    6 let rec fibo = function

    7     | 0 | 1 -> 1

    8     | x -> fibo(x - 1) + fibo(x - 2)

    9 

   10 // generate the first 33 Fibonacci numbers

   11 // using lazy evaluation

   12 let fibs = seq{ for i in 1 .. 33 -> fibo i }

   13 

   14 // filter out even terms

   15 // filter out terms less then 4 million

   16 // add each term together

   17 fibs  |> Seq.filter (fun x -> x % 2 = 0)

   18       |> Seq.filter (fun x -> x < 4000000)

   19       |> Seq.fold   (+) 0

   20 

   21 // the result is: 4613732

Notes:

This was not the best approach to use, in that I sort of cheated to know how many terms I need to iterate to fall in the 4 million range. That is, I got these numbers by trial and error since fibo 32 = 3524578 and fibo 33 = 5702887, I knew that by using 33, I will be in the range needed. However, I will try to address this in a revised version. Since it's been a while since I did F#, I wanted to just knock this one out as quickly as possible. My apologies for the little trick.

[2008.07.06] Project Euler: Problem 1

My goal in this series is to use Functional Programming, namely F# to solve the problems given by Project Euler. As previously stated, I am in the process of learning F# and I thought this would be a good way to illustrate my progress.

Project Euler: Problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Example

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.

Solution 1

This is the long version where everything is nicely laid out and annotated:
NOTE: I will leave running and getting the results to you.

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 1

    5

    6 // create a function sumNumbers that take on argument, n,

    7 //  which represents the upper limit on the numbers we

    8 //  want to sum

    9 //  n = 999 for this problem

   10 let sumNumbers n =

   11     // generate a list of numbers using

   12     //  Sequence Expression,in the

   13     //  input, n, that are multiples of

   14     //  three, five and fifteen 

   15     let multOfThree   = {for x in 1 .. n when x%3=0 -> x}

   16     let multOfFive    = {for x in 1 .. n when x%5=0 -> x}

   17     let multOfFifteen = {for x in 1 .. n when x%15=0 -> x}

   18

   19     // combine the sequences of multiples of 3 and 5

   20     let firstGroup = Seq.append multOfThree multOfFive

   21

   22     // convert the sequence to an array to take advantage

   23     //  of some of array's built in functionality

   24     let arr1 = Seq.to_array firstGroup

   25

   26     // now convert the multiples of 15 to an array

   27     let arr2 = Seq.to_array multOfFifteen

   28

   29     // use the Sum function of array to add

   30     //  members of the array

   31     let sumOfThreeFive = Array.sumByInt (fun a -> a) arr1

   32     let sumOfFifteen   = Array.sumByInt (fun a -> a) arr2

   33

   34     // return the difference between the two array sums

   35     (sumOfThreeFive-sumOfFifteen)

Solution 2

Here is a much simplified version of the solution.

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 2

    5 // this is a much shorter version using

    6 //  lists instead of sequences

    7 // here using List Expressions two lists

    8 //  are created and appended, then the

    9 //  new list is converted to an array

   10 //  and the items summed

   11 // another list with multiples of 15

   12 //  is subtracted from the previous

   13 //  list

   14 (Array.sumByInt

   15     (fun x -> x)

   16     (List.to_array

   17         ([0 .. 3 .. 999]@[0 .. 5 .. 999]))) -

   18 (Array.sumByInt (fun x-> x) [|0 .. 15 .. 999|])

Solution 3

Even more simplified!

    1 #light

    2 // Name: Sparky Dasrath

    3 // Date: 2008.07.06

    4 // Code: Project Euler: Problem 1 - Solution 3

    5 

    6 // this version avoids using the second

    7 //  list of multiples of 15

    8 // the Set operator actually strips out

    9 //  any duplicate values after the lists

   10 //  are combined and the pipeline

   11 //  operator, |> lets you feed values

   12 //  to a function

   13 let a = [0..3..999]@[0..5..999]

   14 Set.of_list a |> Set.to_array |> Array.sumByInt (fun x->x)