Project Euler rocks! I think it’s an especially good way to learn another programming language. I’m planning to try to solve the problems in 2 ways. First, if possible, the brute force method (Which I think helps you to learn the language better) and second, if possible, the formula method (Which I think helps you learn the mathematical concepts better).

Problem #2 states:

Solution 1

So the first approach is using the brute force method where we iterate through all the numbers and determine the next Fibonacci number by adding the last two. I used the Seq.unfold method to do this (Which I discuss further here). Short and sweet:

let max = 4000000
    
let fib = Seq.unfold (fun (last, current) -> Some (last, (current, current + last))) (1, 1)
     
let Run1 _ = 
    fib 
    |> Seq.takeWhile (fun i -> i <= max)
    |> Seq.filter (fun i -> i % 2 = 0)
    |> Seq.fold(fun state item -> state + item) 0
    |> Display.PrintInteger

Solution 2

The second approach actually calculates each Fibonacci number using the Binet formula. Now this is still pretty much brute force in that we still have to iterate from 0 to the max and include only the positive values, but at least we’re using a formula that doesn't require knowledge of the previous values in the sequence. Ron Knott has a nice page on calculating Fibonacci numbers and a “reduced” Binet for calculating positive integers.  The reduced Binet formula is round(φⁿ / √5). The rounding is required because of the irrational numbers in the equation. Theoretically the result would be an integer but because of limits on the number of digits we can calculate, the result will be slightly off and the rounding fixes this. I discuss calculating φ (Or the Golden Ratio) in my last post. Check that out to get a better understanding of how we calculate it.

let max = 4000000

let sqrt5 = sqrt 5.0
let Phi = (1.0 + sqrt5) / 2.0
let fibn n = Phi ** float n / sqrt5 |> round |> int
let fib2 = Seq.unfold (fun index -> Some (fibn index,index + 1)) 1

let Run2 _ = 
    fib2 
    |> Seq.takeWhile (fun i -> i <= max)
    |> Seq.filter (fun i -> i % 2 = 0)
    |> Seq.fold(fun state item -> state + item) 0
    |> Display.PrintInteger

Results

EDIT: After the fact I realized that my original results were skewed by the JIT compiler. Anyways, made some modifications to take this out of the equation and got more accurate results. As you can see in this case that the heavier calculations in solution 2 don’t buy us any performance since we have to iterate through and find the positive numbers starting from 0 anyways. So solution 1 was the best solution in this case. However if we needed to target a specific range of Fibonacci numbers (Especially a high range) the second solution would most definitely win out. 

Patrick McKeague has an excellent video explaining the math behind the golden rectangle. It also explains how to derive the formula for the golden ratio.

First we start with a square like so:

Mark halfway between one of the sides and draw a line from this point to one of the opposite corners. This forms a right triangle.

Now if you were to swing the hypotenuse of this right triangle down to zero degrees of the side of the origin (maintaining the same point of origin) and extend the square to the termination of this line you would get a golden rectangle.

The golden ratio would be the length of this rectangle divided it’s width . We know the width is 2. The length is made up of half of the side of the original square which is 1, plus the hypotenuse of the triangle that was formed above. Using the Pythagorean Theorem (a² + b² = c²) we see that the hypotenuse is:

1² + 2² = c² 
1 + 4 = c² 
c² = 5 
√c² = √5 
c = √5

So the length is 1 + √5. We can then see that the formula for the golden ration is:

1 + √5 
——————  =  φ
   2 

Now the cool thing is if you create a square of any size and follow the above procedure, you will always be able to reduce the equation down to the one above.

I discovered a really cool site called Project Euler (while reading Dustin Campbell's blog) that contains about 250 mathematical problems that you can solve in a programing language of your choice. Once registered you can keep track of the problems you have solved. I've been trying to figure out a way to practice F# and this looks like a fantastic way to do it.

Factoring binomials raised to a particular power can be done easily when you follow a few patterns. We'll use the following binomial to demonstrate these patterns: (2a - b)³. I'm going to do this the long way to illustrate the mechanics.

The first pattern has to do with the power the binomial is raised to. The factored form will first have the original terms multiplied by each other to form a new term. This new term will be added to itself the same number of times as the power of the unfactored binomial plus one; in this example it will be 4 (3 + 1). Since the operation in the unfactored binomial is subtraction the second term, b, will be negative.

(2a)(-b) + (2a)(-b) + (2a)(-b) + (2a)(-b)

The next pattern involves the coefficients. The coefficients for each term in the factored binomial match a row in Pascal's Triangle. The row number we want in Pascal's Triangle is the power the unfactored binomial was raised too (With the first row in the triangle being zero). So in this example the binomial is raised to the 3rd power and the coefficients will match the values in row 3 of Pascal's Triangle: 1, 3, 3 and 1 in that order.

1(2a)(-b) + 3(2a)(-b) + 3(2a)(-b) + 1(2a)(-b)

The next pattern involves the powers of the terms. The first term in the original unfactored binomial, 2a, starts with the power of the original unfactored binomial and decreases by one, in the factored form. The second term in the original unfactored binomial, b, starts with a power of zero and increases by one, in the factored form.

1(2a)³(-b)⁰ + 3(2a)²(-b)¹ + 3(2a)¹(-b)² + 1(2a)⁰(-b)³

Now the factored form can be reduced. First, if the terms in the unfactored binomial are subtracted, every other operation in the factored binomial will be subtraction. This occurs because the power determines the sign of the term. Negative terms raised to an even number will be positive (IE: -2² == -2 * -2 == 4) and negative terms raised to an odd power will remain negative (IE: -2³ == -2 * -2 * -2 == -8). The pattern ends up being the first first operation is subtraction, the second is addition and so on.

1(2a)³(b)⁰ - 3(2a)²(b)¹ + 3(2a)¹(b)² - 1(2a)⁰(b)³

Now reduce the terms:

8a³ - 12a²b + 6ab² - b³

So a binomial raised to the third power, (a + b)³, will follow this pattern:

a³ + 3a²b + 3ab² + b³

The following script will factor out binomials (at least to a certain degree):

MathTV is posting videos on YouTube (Teasers for their service). There are over 60 so far on a number of different topics. MathTV also has an online subscription for $35 a year which gives you access to hundreds of videos. I like that they are under 10 minutes each and the instructor does a great job of explaining the material.

The following JavaScript class enables you to get the expanded coefficients of a binomial raised to a particular power. Pass in the power and it will return an array of coefficients. For example, passing in a power of 6 returns {1, 6, 15, 20, 15, 6, 1}. This is also a row in Pascal's Triangle. It's using the following formula to calculate the coefficients, where n is the the power the binomial is raised to and k is the term position (0 to n).

Here is the class (PascalsTriangle.js):

function PascalsTriangle()
{
    this.GetExpandedBinomialCoefficients = function(power)
    {
        var coefficients = new Array(power);

        for (var index = 0; index <= power; index++)
        {
            coefficients[index] = this.GetExpandedBinomialCoefficient(power, index);
        }

        return coefficients;
    }

    this.GetExpandedBinomialCoefficient = function(power, term)
    {
        return this.GetFactorial(power) / (this.GetFactorial(term) * this.GetFactorial(power - term));
    }

    this.GetFactorial = function(value)
    {
        if (value <= 1)
            return 1;
        else
            return value * this.GetFactorial(value - 1);
    }
}

The class can be used as follows:

var pascalsTriangle = new PascalsTriangle();
var coefficients = pascalsTriangle.GetExpandedBinomialCoefficients(6);
alert(coefficients.join(' '));

This video covers Pascal's Triangle...

I have been wanting to dig into F# for quite some time and finally got an opportunity. My first stab at it implements the calculation of kinetic energy given a weight in lbs, speed in mph and output in kJ. Pretty basic, but ya gotta start some where right? :)

KineticEnergy.zip (.95 KB)

// Get info from the user
do Printf.printf "Enter the weight (LBS): "
let m = read_line()
do Printf.printf "Enter the velocity (MPH): "
let mph = read_line()

// Pound to kilogram conversion
let kg lbs = lbs / 2.2

// Miles/h to Meters/s conversion
let mps mph = (((mph * 1.6) * 1000.0) / 60.0) /60.0

// Kinetic energy calculation
let Ek m v = (0.5 * m * (v * v)) / 1000.0

// Show me the money
do Printf.printf "\nEk = %fkJ\n\n" (Ek (kg (float_of_string m)) (mps (float_of_string mph)))

// Wait! Let me see the answer...
do Printf.printf "Press enter to continue..."
let x = read_line()

A while ago I posted a link to MIT's Open Courseware (OCW) site. Recently I have begun to make use of it and wanted to share some of what I have found. First of all, it rocks! It really is a great resource, especially for those who want to learn about a subject and would like to do self study. I didn’t realize this earlier but a number of the courses also publish videos of the lectures. For example 3.091, "Introduction to Solid State Chemistry" has all 35 lectures posted, thats almost 30 hours of lecture time! These videos (If available) can be found possibly in 3 locations, so keep that in mind. The first is on the OCW site. Browse to the course you are interested in, for example Introduction to Solid State Chemistry. Under the "Lecture Notes" (This label may be a little different between courses) section you will find the video streams and the lecture notes. The second location is on the regular class page. 3.091 has a tab called "Videos" and another called "Archives", both have links to lecture videos and notes. Now the third place you can check, if you want to easily download the videos, is Google Video. Searching for "3.091" brings up all but 2 of the course videos which can be downloaded in in a format that can be played by your video IPod. Actually Google Video has over 450 MIT Lectures available for download! There are also nearly 300 UC Berkeley lectures as well. If you want to download any of the lecture videos (to your hard disk) that are offered as a stream on the MIT website you can use a program like FlashGet to save the stream as a file and then convert the file to what you want. The MIT site publishes RealVideo streams (That use the RTSP protocol).

Other courses that offer video lectures are (To name a few):

Physics - Electricity and Magnetism
Physics - Vibrations and Waves
Physics - Classical Mechanics
Physics - General Relativity
Mathematics - Differential Equations
Mathematics - Linear Algebra
Chemistry - Principles of Chemical Science
Chemistry - Solid Sate Chemistry
Biology - Introductory Biology
Computer System Engineering
Circuits and Electronics
Atomistic Computer Modeling of Materials
Media, Education, and the Marketplace
Electromagnetics and Applications

You may want to look on the course listing to see if there is a newer version of the course as newer ones are periodically added.

The OCW site also offers the course syllabus, study materials, readings, exams and a number of other resources. They offer the option to download the entire course as a zip file so that you don’t have to download the resources individually.

Now a few words about the "Introduction to Solid State Chemistry" (3.091) course... If you are interested in learning about chemistry I would highly recommend the 3.091 course. Donald Sadoway is the lecturer for this course and he does an amazing job! You can tell he loves the subject and he knows it very well. He has a great sense of humor and he really makes the material come alive (At least for me anyways). This course lays an excellent foundation for other areas of study.

Unary operations only have one input while binary operations have two inputs. For example ++i is a unary operation since this statement only has one input value, i. On the other hand i + n is a binary operation (Not to be confused with the binary numeral system) since there are two inputs, i and n. i + n + z is still binary since it is actually 2 binary operations; i + n = x, then x + z = y or (i + n) + z.