You are currently browsing the tag archive for the ‘Farey sequence’ tag.

This is a mini investigation based on the current Nrich task Farey Sequences.

As Nrich explains:

I’m going to look at Farey sequences (though I won’t worry about rearranging them in order of size). Here are some of the first Farey sequences. The missing fractions are all ones which simplify to a fraction already on the list (e.g. 2/4 is missing because this is the same as 1/2)

You should be able to notice that the next Farey sequence always contains the previous Farey sequence, so the problem becomes working out which of the new fractions added will not cancel down to something already on the list.

**Highest Common Factors**

Fractions will not cancel down (simplify) if the numerator and denominator have a highest common factor (HCF) of 1. For example 2/4 simplifies because the highest common factor of 2 and 4 is 2. Therefore both top and bottom can be divided by 2. 4/5 does not simplify because the HCF of 4 and 5 is 1.

We call 2 numbers which have a HCF of 1 **relatively prime.**

for example for the number 4: 1 and 3 are both relatively prime (HCF of 1 and 4 =1, HCF of 3 and 4 = 1).

**Relatively prime numbers**

2: 1

3: 1,2

4: 1,3

5: 1,2,3,4

6: 1,5

7: 1,2,3,4,5,6

8: 1,3,5,7

9: 1,2,4,5,7,8

You might notice that these give the required numerators for any given denominator – i.e when the denominator is 9, we want a numerator of 1,2,4,5,7,8.

**Euler totient function**

Euler’s totient function is a really useful function in number theory – which counts the number of relatively prime numbers a given number has. For example from our list we can see that 9 has 6 relatively prime numbers.

Euler’s totient function is defined above – it’s not as complicated as it looks! The strange symbol on the right hand side is the product formula – i.e we multiply terms together. It’s easiest to understand with some examples. To find Euler’s totient function we first work out the prime factors of a number. Say we have the number 8. The prime factors of 8 are 2^{3}. Therefore the only unique prime factor is 2.

Therefore the Euler totient function tells me to simply do 8 (1 – 1/2) = 4. This is how many relatively prime numbers 8 has.

Let’s look at another example – this time for the number 10. 10 has the prime factorisation 5 x 2. Therefore it has 2 unique primes, 2 and 5. Therefore the Euler totient function tells me to do 10(1-1/2)(1-1/5) = 4.

One more example, this time with the number 30. This has prime factorisation 2 x 3 x 5. This has unique prime factors 2,3,5 so I will do 30(1 -1/2)(1-1/3)(1-1/5) =8.

**An equation for the number of fractions in the Farey sequence**

Therefore I can now work out how many fractions will appear in a given Farey sequence. I notice that for (say) F_{5} I will add Euler’s totient for n = 2, n = 3, n = 4 and n = 5. I then add 2 to account for 0/1 and 1/1. Therefore I have:

For example to find F_{6}

There are lots of things to investigate about Farey functions – could you prove why all Farey sequences have an odd number of terms? You can also look at how well the Farey sequence is approximated by the following equation:

For example when n = 10 this gives:

and when n = 1000 this gives:

These results compare reasonably well as an estimation to the real answers of 33 and 304,193 respectively.

**IB Revision**

If you’re already thinking about your coursework then it’s probably also time to start planning some revision, either for the end of Year 12 school exams or Year 13 final exams. There’s a really great website that I would strongly recommend students use – you choose your subject (HL/SL/Studies if your exam is in 2020 or Applications/Analysis if your exam is in 2021), and then have the following resources:

The Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and each area then has a number of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!

The Practice Exams section takes you to ready made exams on each topic – again with worked solutions. This also has some harder exams for those students aiming for 6s and 7s and the Past IB Exams section takes you to full video worked solutions to every question on every past paper – and you can also get a prediction exam for the upcoming year.

I would really recommend everyone making use of this – there is a mixture of a lot of free content as well as premium content so have a look and see what you think.