0 1 1 2 3 5 8 13 ...

This program makes an array (or list) of all the fibonacci numbers up to the one we ask for.

This line adds the sum of the last item and the the last-but-one item to the end of the list.

Can you see how it works?

What's the next number?

This version just finds each new value and "forgets" the old ones!

Store a + b in c

Store b in a

Now put c in b

... and we are ready to go again.

Factorial n!

The factorial is an integer multiplied by all the integers less than it, stopping at 1.

For example:

5! is 5 x 4 x 3 x 2 x 1 = 120

Averages

Square Roots

Heron of Alexandria came up with a great algorithm for finding square roots.

1. Make a guess.

2. Check it (by squaring it).

3. If it's not accurate enough, try the average of the guess plus x.

4. Repeat.

For example ... the square root of 10.

We know the square root of 9 is 3, so we could guess 3.

3 x 3 is 9.

(3 + 10/3) / 2 = 3.1666...

3.1666... squared is 10.027777...

(3.1666 + 10/ 3.1666) / 2 = 3.162228

3.162228 squared is 10.0000192367

We are getting close to the answer, you just stop when you are close enough!

Here's Scratch working out the square root of 9!

Prime Numbers

You may have used something like Eratosthenes' Sieve to find prime numbers.

This program works in the same way.

It counts up from wherever you ask it to and finds a certain number of primes.

To save time, we only use prime numbers for our test divisors.

It's a prime if we have gone past the square root of the number.

If the number divides without a remainder, it's not a prime, so we try the next (odd) number.

Change the counter (so we are using the next prime divisor).

Sir Isaac Newton came up with a good way to find the "roots" of equations - the value of x that will give 0.

This is a simplified version that finds one of the roots of a quadratic equation.

It's a little bit like Heron of Alexandria's method for finding square roots.

quad = ax^2 + bx + c

deriv = 2ax + b

In this version we just keep going until the last answer is the same as the current one!

If we are not close enough, we use the current root minus the result of the quadratic equation divided by the derivative.

Here, I started the program with a higher "guess" and it found the other root!

The derivative gives us the slope of the line at a point:

-6 at x = -1

6 at x = 5

Project Euler

http://projecteuler.net

This website hosts a series of Maths problems to be solved by writing computer programs.

Problem 1:

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.

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, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

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

James Gregory (1638 – 1675)

Scottish mathematician.

He discovered this theory (values less than 1):

Leonhard Euler (1707 - 1783)

Swiss mathematician.

He discovered this formula for Pi:

It turns out you can expand the even-numbered Fibonacci values as follows:

or

We can continue expanding the even-numbered terms until we get an infinite series like this:

**If we have a circle of radius 1:**

**Radians**

**Radians are another way of talking about angles.**

Radians measure the length of the arc, so for a whole circle:

Radians measure the length of the arc, so for a whole circle:

**Tangent and arctan**

**Tangents tell us the slope of an angle.**

Tan of 45 degrees is 1 (eg 1cm up for every cm right).

Arctan is the inverse of tan.

Arctan of 1 is 45 degrees or pi/4 radians.

So the arctan of 1 will give us pi/4.

Tan of 45 degrees is 1 (eg 1cm up for every cm right).

Arctan is the inverse of tan.

Arctan of 1 is 45 degrees or pi/4 radians.

So the arctan of 1 will give us pi/4.

**We can use Gregory's series to compute pi, but it converges (gets accurate) very slowly.**

This is why we use Euler's formula (and especially the expansion of it).

Computing the smaller values, 1/2, 1/5 etc is much more efficient as they converge more quickly.

This is why we use Euler's formula (and especially the expansion of it).

Computing the smaller values, 1/2, 1/5 etc is much more efficient as they converge more quickly.