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.

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):

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...