How to Find Perfect Numbers with F#

"But no perfection is so absolute, That some impurity doth not pollute."
-- The Rape of Lucrece Ver. 124 by William Shakespeare

"It is reasonable to have perfection in our eye ; that we may always advance towards it"
-- Samuel Johnson in letters to The Adventurer

Few things in life can be said to be perfect, but in mathematics there do exist numbers which are said to be perfect.  A perfect number is a number who's sum of its divisors (other than its self) is equal to its self.  

For exemplification, the number 6 is a perfect number.  Why is 6 perfect?

• 6 is divisible by 1
• 6 is divisible by 2
• 6 is divisible by 3

The sum of 1, 2, and 3 is 6 (e.g. 1 + 2 + 3 = 6).  Thus by the definition of a perfect number given above, 6 is a perfect number.  In fact 6 is the first perfect number (1 is never include in the realm of special numbers).

In order to say that a number is perfect we would need to do the following.

1. Find all of the divisors of the given number
2. Sum up the divisors found in step 1
3. Compare the sum found in step 2 to the input

Above is an example of what the flow would look like with the number 6.  We would take the numbers 1 - 5 as a list of possible divisors.  Filter down to 1, 2, and 3.  Sum 1, 2, and 3 giving us 6.  Last comparing the sum we got from the summing step to the input.  Since 6 equals 6, we would return true.

Hmmm, step 1 sounds a lot like a filter and step 2 sounds like folding.  I bet we can write a simple F# function that can find perfect numbers using a filter and a fold (using fsi.exe and Mono).

> let isPerfect x =

-   match x with

-   | x when x <= 1 -> false

-   | _ -> [1 .. x-1] |> List.filter (fun n -> x % n = 0) |> List.sum = x

- ;;

val isPerfect : int -> bool

In the function above we pattern match anything less than and including 1 as false, since by definition those numbers are not perfect numbers (if we wanted we could go up to and including 5 since 6 is the first perfect number).  Succeeding we just need to create a list of numbers up to the number x that we are checking for perfection.  We take this list and filter out the numbers that are not divisors leaving just the divisors.  Then we use the built in folding of summing with the List.sum function.  Finally we compare the sum of the divisors against the input number x.

Now lets test out the function with the perfect numbers 6, 28, and 496.  We'll also test with the less than perfect numbers of 5 and 99.

> isPerfect 6;;

val it : bool = true

> isPerfect 28;;

val it : bool = true

> isPerfect 496;;

val it : bool = true

> isPerfect 5;;  

val it : bool = false

> isPerfect 99;;

val it : bool = false

In fact if we wanted to we could use this function with List.filter against all of the numbers from 1 to 9999!

> [1 .. 9999] |> List.filter isPerfect

- ;;

val it : int list = [6; 28; 496; 8128]

That is in fact the first 4 perfect numbers which were known to the Greeks.

Note, this code is made to be readable not to be fast a few changes should be made to make it fast.

The Last of the Big 3 Higher-Order Functions - Folding

In functional programming, the big 3 higher-order functions are: mapping, filtering, and folding.  This blog post is on the last, folding.

Folding is typically used to apply a function to a list of data obtaining a single result.  Consider the summing up of a list of numbers, the addition routine could be applied using a fold against a list yielding a single number as the result.

Given the image above, we have a list of numbers (9, 4, 2, 4) and a magenta function "Adder" which takes the list of numbers and applies the adder function against them giving us the single output value of 19.

The way in which folding takes place can be thought of as the following.

1. Adder 9 4 = 13
2. Adder 13 2 = 15
3. Adder 15 4 = 19

Or if you dislike that manner of notation.

1. 9 + 4 = 13
2. 13 + 2 = 15
3. 15 + 4 = 19

Typically in functional programming languages there are many different ways to fold a function against a list.  In the F# examples which will follow, we'll use fold and reduce, the only difference between the two (at least the only one I know of) is that fold requires an initial value for the function to be applied to, while reduce uses the head of the list as the initial value.

Note that we are using fsi.exe running on Mono.

Given a list of number (x), sum up the values (using 0 as the initial value)


> let x = [4398; 233; 1; 34; 42; 8392; -8];;

val x : int list = [4398; 233; 1; 34; 42; 8392; -8]

> x |> List.fold (+) 0
- ;;
val it : int = 13092

Using reduce gives the same value (and does not require an initial value)


> let x = [4398; 233; 1; 34; 42; 8392; -8];;

val x : int list = [4398; 233; 1; 34; 42; 8392; -8]

> x |> List.fold (+) 0
- ;;
val it : int = 13092
> x |> List.reduce (+)
- ;;
val it : int = 13092

Similarly, we can use folding to find the max and min values (same x as before).


> let x = [4398; 233; 1; 34; 42; 8392; -8];;

val x : int list = [4398; 233; 1; 34; 42; 8392; -8]

> x |> List.reduce (max)
- ;;
val it : int = 8392
> x |> List.reduce (min)
- ;;
val it : int = -8

As you have witness from the code above, folding can be used to apply a function which takes two arguments against a list of values producing one resulting value.  Folding is a very useful tool in the functional programming tool belt and is one of the big 3 higher-order functions.

Evens with a Filter

One of the most common "tools" in the functional programming tool belt is the filter.  A filter is typically a function which applied to remove elements a list.

Given the image above, the light green filter called Evens which filters out the member of the list which are not even, in this case out of the list [3; 4; 5; 6] only the members [4; 6] survive the filter.

Note in a language like F# which is immutable the list the filter returns is a new list.

If we want to filter out all of the odd numbers from 1 to 100 we could do the following in F# (using fsi.exe running against Mono).


> let x = [ 1 .. 100 ];;

val x : int list =
  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
   22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
   41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
   60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
   79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
   98; 99; 100]

> let evens x =
-   match x with
-   | x when x % 2 = 0 -> true
-   | _ -> false;;

val evens : int -> bool

> x |> List.filter evens
- ;;
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; 38; 40;
   42; 44; 46; 48; 50; 52; 54; 56; 58; 60; 62; 64; 66; 68; 70; 72; 74; 76; 78;
   80; 82; 84; 86; 88; 90; 92; 94; 96; 98; 100]

In our code above we have a list x which has the values 1 through 100 in it.  We likewise have a function called evens which returns true or false based on if the value passed in is divisible by 2.  We conclude with List.filter utilizing our function evens against every member of list x, if evens returns true that element of x is passed to the output list.  Hence with any function which returns a bool, we can encumber that function to a list using List.filter and filter out any undesirable elements.

Getting Sound to Work Again on Ubuntu 12.04

Well, it happen again--I did what I thought would be some simple updates on my Dell Vostro 1500 running Ubuntu 12.04 and boom--no sound!  I did a little googling and found this very useful write up.

I was unable to get anything to work (but I understood what the issue was by following the steps in the write up), then I come across the section titled: Getting the ALSA drivers from a *fresh* kernel.

I performed the following commands to freshen up my ALSA drivers.

sudo apt-get --purge remove linux-sound-base alsa-base alsa-utils

sudo apt-get install linux-sound-base alsa-base alsa-utils

sudo apt-get install gdm ubuntu-desktop

aplay -l

After running aplay -l and subsequently seeing that my drivers looked secured, I head back to The Casters YouTube video on Terminal and Initial Objects that I want to watch and was happy to listen to audio again!  Thank you LordRaiden!

FizzBuzz using a mapping

In functional programming one of the most used "tools" is the mapper.  The mapper is typical used to apply a function to elements of a list.

Using the image above we can imagine that we have a mapper which takes elements and changes the color to magenta, thus the blue circle A would be mapped to a magenta circle A, B to B, and C to C.  

Note that only the color has been changed.

If we want to do FizzBuzz in F# using a mapper we could do the following (using fsi.exe running against Mono).

> let x = [ 1 .. 31 ];;

val x : int list =

  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;

   22; 23; 24; 25; 26; 27; 28; 29; 30; 31]

> let fizzBuzzer x = 

-  match x with 

-  | x when x % 15 = 0 -> "FizzBuzz"

-  | x when x % 3 = 0 -> "Fizz"

-  | x when x % 5 = 0 -> "Buzz"

-  | x -> x.ToString()

- ;;

val fizzBuzzer : int -> string

> x |> List.map fizzBuzzer;;

val it : string list =

  ["1"; "2"; "Fizz"; "4"; "Buzz"; "Fizz"; "7"; "8"; "Fizz"; "Buzz"; "11";

   "Fizz"; "13"; "14"; "FizzBuzz"; "16"; "17"; "Fizz"; "19"; "Buzz"; "Fizz";

   "22"; "23"; "Fizz"; "Buzz"; "26"; "Fizz"; "28"; "29"; "FizzBuzz"; "31"]

In the code above, our list of numbers is x which holds the numbers 1 through 31.  We also have a function called fizzBuzzer which takes an int and outputs a string based on the typical FizzBuzz rules.  Last we use List.map to do a mapping of fizzBuzzer against x giving us a list of strings with the FizzBuzz rules applied.

Note, we could have done this very easily in one line of F#.