My Thoughts on Software Development

Cool Coursera Course: Pre-Calculus

Course Description

This course is designed to prepare you for a college-level Calculus course. Through this course you will acquire a solid foundation in algebra and trigonometry. Emphasis is placed on understanding the properties of linear, polynomial, rational, radical, piece-wise, exponential, logarithmic, and trigonometric functions. You will learn to work with various types of functions in symbolic, graphical, numerical and verbal form.

This course will be taught over ten weeks, with materials released on a weekly basis. Each week will consist of a series of short lecture videos, quizzes every 3-5 lectures, readings and homework assignments through which you can practice your mastery of the material.

A prerequisite background in Introductory Algebra and Basic Geometry is necessary for this course.

Pre-Calculus by Dr. Sarah Eichhorn, Dr. Rachel Cohen Lehman

Project Euler: Solution to Problem 6

Sum square difference

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385.

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 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. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

On my previous post about how to solve problem 1 we saw that it is possible to represent a summation of all the natural numbers in a polynomial form.

You could solve this problem pretty much the same way you solved problem 1, using brute force:

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
require 'test/unit'

def sum_of_natural_numbers(n)
  (1..n).inject(:+)
end

def sum_of_square_of_natural_numbers(n)
  (1..n).inject { |memo, number| memo + (number ** 2) }
end

def solve(n)
  (sum_of_natural_numbers(n) ** 2) - sum_of_square_of_natural_numbers(n)
end

class TestProblem6 < Test::Unit::TestCase
  def test_sum_of_the_first_ten_natural_numbers_should_be_55
    assert_equal(55, sum_of_natural_numbers(10))
  end

  def test_sum_of_square_of_the_first_ten_natural_numbers_should_be_385
    assert_equal(385, sum_of_square_of_natural_numbers(10))
  end

  def test_the_sum_square_difference_of_the_first_ten_natural_numbers_should_be_2640
    assert_equal(2640, solve(10))
  end

  def test_the_sum_square_difference_of_the_first_one_hundred_natural_numbers_should_be_25164150
    assert_equal(25164150, solve(100))
  end
end

Doing a little bit of research, we could discover that this problem was solved back in 1631 by Johann Faulhaber, who published the general formula to the power sum of the first n positive integers:

images

Also know as square pyramidal numbers, it is possible to express the sum of powers of 2 as:

images

That can be translated to the following Ruby code:

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
require 'test/unit'

def sum_of_natural_numbers(n)
  ((n ** 2) + n) / 2
end

def sum_of_square_of_natural_numbers(n)
  ((2 * (n ** 3)) + (3 * (n ** 2)) + n) / 6
end

def solve(n)
  (sum_of_natural_numbers(n) ** 2) - sum_of_square_of_natural_numbers(n)
end

class TestProblem6 < Test::Unit::TestCase
  def test_sum_of_the_first_ten_natural_numbers_should_be_55
    assert_equal(55, sum_of_natural_numbers(10))
  end

  def test_sum_of_square_of_the_first_ten_natural_numbers_should_be_385
    assert_equal(385, sum_of_square_of_natural_numbers(10))
  end

  def test_the_sum_square_difference_of_the_first_ten_natural_numbers_should_be_2640
    assert_equal(2640, solve(10))
  end

  def test_the_sum_square_difference_of_the_first_one_hundred_natural_numbers_should_be_25164150
    assert_equal(25164150, solve(100))
  end
end

If you see any flaw with that solution, or ways to improve it, please send me a pull request!

Project Euler: Solution to Problem 2

Even Fibonacci numbers

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrent relation:

images

With the seed values:

images

A recursive algorithm

In general, any recursive algorithm such as the Fibonacci gives us a recurrence relation.

The Fibonacci formula seems to give us a natural example of recursion:

1
2
3
4
5
def fib(n)
  return 1 if n <= 2

  fib(n - 1) + fib(n - 2)
end

The complexity of a naive recursive Fibonacci is 2n, since in each step you call the function F twice:

images

Given that, the worse way to solve that problem would be:

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
require "test/unit"

def solve(limit)
  sum_of_even_valued_terms = 0
  n = 0

  while (true)
    fib_value = fib(n)

    if (fib_value > limit)
      break
    end

    if (fib_value % 2 == 0)
      sum_of_even_valued_terms += fib_value
    end

    n += 1
  end

  sum_of_even_valued_terms
end

def fib(n)
  return 1 if n <= 2

  fib(n - 1) + fib(n - 2)
end

class TestProblem2 < Test::Unit::TestCase
  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_20_should_be_10
    assert_equal(10, solve(20))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_50_should_be_44
    assert_equal(44, solve(50))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_200_should_be_118
    assert_equal(188, solve(200))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_4000000_should_be_4613732
    assert_equal(4613732, solve(4000000))
  end
end

We could do a simple optimization, and calculate only the even-valued fibonacci numbers. Given F(3) = 2, F(6) = 8, F(9) = 34 and F(12) = 144, then:

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
require "test/unit"

def solve(limit)
  sum_of_even_valued_terms = 0
  # the first even-valued fibonacci number
  n = 3

  while (true)
    even_valued_term = fib(n)

    if (even_valued_term > limit)
      break
    end

    sum_of_even_valued_terms += even_valued_term

    # the next even-valued member
    n += 3
  end

  sum_of_even_valued_terms
end

def fib(n)
  return 1 if n <= 2

  fib(n - 1) + fib(n - 2)
end

class TestProblem2 < Test::Unit::TestCase
  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_20_should_be_10
    assert_equal(10, solve(20))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_50_should_be_44
    assert_equal(44, solve(50))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_200_should_be_118
    assert_equal(188, solve(200))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_4000000_should_be_4613732
    assert_equal(4613732, solve(4000000))
  end
end

Dynamic Programming

The reason why our previous recursive algorithm is slow is because it keeps recomputing the same subproblems over and over again. You could avoid that problem by using a simple memoization algorithm that will help us avoid wasting effort computing every subproblem again.

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
require "test/unit"

def solve(limit)
  sum_of_even_valued_terms = 0
  # the first even-valued fibonacci number
  n = 3

  while (true)
    even_valued_term = fib(n)

    if (even_valued_term > limit)
      break
    end

    sum_of_even_valued_terms += even_valued_term

    # the next even-valued member
    n += 3
  end

  sum_of_even_valued_terms
end

def fib(n)
  f = Array.new(n + 1)
  f[1] = f[2] = 1

  (3..n).each do |i|
    f[i] = f[i-1] + f[i-2];
  end

  f[n]
end

class TestProblem2 < Test::Unit::TestCase
  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_20_should_be_10
    assert_equal(10, solve(20))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_50_should_be_44
    assert_equal(44, solve(50))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_200_should_be_118
    assert_equal(188, solve(200))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_4000000_should_be_4613732
    assert_equal(4613732, solve(4000000))
  end
end

Matrix Multiplication

This is basically a mathematical trick with matrices. That matrix generates the F(n) and F(n+1) terms of the Fibonacci sequence:

images

The formula for multiplying two symmetric 2x2 matrices:

images

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
require 'test/unit'

def solve(limit)
  sum_of_even_valued_terms = 0
  # the first even-valued fibonacci number
  n = 3

  while (true)
    even_valued_term = fib(n)

    if (even_valued_term > limit)
      break
    end

    sum_of_even_valued_terms += even_valued_term

    # the next even-valued member
    n += 3
  end

  sum_of_even_valued_terms
end

def fib(n)
  matrix = [
    [1, 0],
    [0, 1],
  ]

  matrix = matrix_power(matrix, n - 1)

  matrix[0][0]
end


# This is recursive method tries to compute the nth power of A by squaring the (n/2)th power.
def matrix_power(matrix, n)
  if (n > 1)
    matrix = matrix_power(matrix, n / 2)
    matrix = multiply_matrix(matrix, matrix)
  end

  # However if n is odd, rounding down n/2 and squaring that power of A results in the (n-1)st power, 
  # which we "fix up" by multiplying one more factor of A.
  if (n % 2 != 0)
    matrix = multiply_matrix(matrix, [[1, 1], [1, 0]])
  end

  matrix
end

def multiply_matrix(mat1, mat2)
  [
    [
      mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0],
      mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]
    ],
    [
      mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0],
      mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1]
    ]
  ]
end

class TestProblem2 < Test::Unit::TestCase
  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_20_should_be_10
    assert_equal(10, solve(20))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_50_should_be_44
    assert_equal(44, solve(50))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_200_should_be_118
    assert_equal(188, solve(200))
  end

  def test_the_sum_of_the_even_valued_terms_of_fibonacci_that_do_not_exceed_4000000_should_be_4613732
    assert_equal(4613732, solve(4000000))
  end
end

This algorithm is based on the idea of exponentiation by squaring and It turns out that this solves in O(log n).

If you see any flaw with that solution, or ways to improve it, please send me a pull request!

Project Euler: Solution to Problem 1

Multiples of 3 and 5

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.

The thing with Project Euler is that there is usually an obvious brute force way to solve the problem, which will take about forever! As the questions become more difficult, you will need to implement clever solutions.

This problem is easily solvable using the following Ruby code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
require "test/unit"

def solve(n)
  (0...n).reduce do |memo, obj|
    obj % 3 == 0 || obj % 5 == 0 ? memo + obj : memo
  end
end

class TestProblem1 < Test::Unit::TestCase
  def test_the_sum_of_the_multiples_of_3_and_5_below_10_should_be_23
    assert_equal(23, solve(10))
  end

  def test_the_sum_of_the_multiples_of_3_and_5_below_20_should_be_78
    assert_equal(78, solve(20))
  end

  def test_the_sum_of_the_multiples_of_3_and_5_below_1000_should_be_233168
    assert_equal(233168, solve(1000))
  end
end

The problem with solving the problem that way is that you need to iterate over every single number between 0 and 999. Given that, the complexity of this code is O(n).

There is a better way to solve that problem using proper Math, and with a complexity of O(1) (assuming arithmetic operation are implemented in O(1)).

In combinatorial mathematics, the Inclusion–exclusion principle is a counting technique, which generalizes the familiar method of obtaining the number of elements in the union of two finite sets, symbolic expressed as:

images

The value of the summation can be found without performing a thousand iterations, since it can be shown (for instance by mathematical induction) that the number of elements in the union of two finite sets, symbolic expressed as:

images

Let’s try to prove that using a small problem:

Find the sum of all the multiples of 3 or 5 below 20.

if we list, by hand, all the natural numbers below 20 that are multiples of 3 or 5, we get: 3, 5, 6, 9, 10, 12, 15 and 18. The sum of these multiples is 78.

Now, let’s apply the previous formula to solve that:

images

Now that we know that this formula works, it can be translated to the following Ruby code:

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
require "test/unit"

def solve(n)
  k1 = 3
  k2 = 5
  k3 = 15

  sum3 = sum_of_multiples(k1, n)
  sum5 = sum_of_multiples(k2, n)
  sum15 = sum_of_multiples(k3, n)

  sum3 + sum5 - sum15
end

def sum_of_multiples(multiple, limit)
  b = (limit - 1) / multiple
  multiple * ((b * (b + 1))/2)
end

class TestProblem1 < Test::Unit::TestCase
  def test_the_sum_of_the_multiples_of_3_and_5_below_10_should_be_23
    assert_equal(23, solve(10))
  end

  def test_the_sum_of_the_multiples_of_3_and_5_below_20_should_be_78
    assert_equal(78, solve(20))
  end

  def test_the_sum_of_the_multiples_of_3_and_5_below_1000_should_be_233168
    assert_equal(233168, solve(1000))
  end
end

If you see any flaw with that solution, or ways to improve it, please send me a pull request!