 Write a program to compute X(k) defined by:  Compute X(100), and suggest a plausible value for X(k) as k goes to infinity. If you think you've solved it, or if you're stuck, email pi3challenge@sheffield.ac.uk or tweet to @pi3challenge The answer can be found here. What is a Farey sequence? John Farey, a British geologist and writer from the Napoleonic era, is credited with devising a simple sequence which takes his name. How do we make a Farey sequence? First, consider all fractions less than 1 with denominator less than or equal to k. Let's take k=6 as an example, i.e. 1/2, 1/3, 2/3, 1/4, 2/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 2/6, 3/6, 4/6, 5/6. Note that some of these fractions are equal: 2/4 = 3/6 = 1/2, and 2/6 = 1/3 and 4/6 = 2/3. Let's remove the duplicates, and rearrange the remaining fractions in ascending order: 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6. This is the Farey sequence of order k = 6. It has 11 elements, so N(6) = 11. [It is intriguing that each fraction in the ascending sequence can be found from the fractions on either side: simply take the sum of the numerators, and divide by the sum of the denominators! For example, 1/3 = (1 + 2)/(4 + 5) = 3/9 = 1/3.] |
Mini-Challenges >