February 2019

[SmartMersenne]

Originally Posted by c10ck3r

Any tips on pseudocode to identify the endpoint? I think I figured out the rest on my own.

Can you be more specific?

[Xyzzy]

http://www.research.ibm.com/haifa/po...ruary2019.html

[Dr Sardonicus]

A summary of the history of "Farey sequences" and the basic mathematical results may be found here.

I give a couple of results here. I make the general assumption that the denominators of fractions are positive integers, and the numerators are either 0 or positive integers.

Result 1: If a/b < p/q < c/d, and p*b - a*q = c*q - p*d, then p/q = (a+c)/(b+d).

Proof: Rearranging terms gives

p*b + p*d = a*q + c*q, or

p*(b + d) = q*(a + c). Dividing by (q*(b + d)) gives the result.

----------------

Result 2: If a/b < c/d, c*b - a*d = 1, and a/b < p/q < c/d, then q >= b + c.

Proof: We have

c/d - a/b = p/q - a/b + c/d - p/q =

(p*b - a*q)/(q*b) + (c*q - p*d)/(q*d), so that

c/d - a/b >= 1/(q*b) + 1/(q*d). Multiplying through by q*b*d,

q*(b*c - a*d) >= d + b. Since b*c - a*d = 1, we have

q >= b + d.

These two results lead to a proof by induction that, starting with the "Farey sequence" F₁ = [0/1, 1/1], the succeeding Farey sequence F_n+1 is formed by inserting between consecutive fractions a/b < c/d the "mediant" fraction (a + c)/(b + d), provided b + d = n+1. In every case, consecutive fractions satisfy the hypotheses of Result 1, so the mediant has the smallest denominator of any fraction between a/b and c/d.

The above results also lead to an induction proof that, in every Farey sequence F_n, the denominator of any fraction between two consecutive terms is larger than that of either term (in fact, at least as large as their sum). This result may (at least in theory) have some bearing on the March 2019 challenge.

They also lead to a computationally straightforward method of constructing the Farey sequence F_n. We know that the first two terms are 0/1 and 1/n. We also know by Result 1 that, given two consecutive terms a/b and p/q, the next term c/d is such that

p/q = (a + c)/(b + d). That is, for some positive integer k,

a + c = p*k, and b + d = q*k, or

c = p*k - a, and d = q*k - b.

Now, since we want to make sure we obtain all fractions with denominator up to n, we want

n - q < q*k - b <= n, or

n - q + b < q*k <= n + b, or

(n + b)/q - 1 < k <= (n + b)/q, that is

k = floor((n+b)/q).

We then have the next fraction c/d, and can then use p/q and c/d as our fractions, and repeat the process. The calculation continues until the denominator becomes 1, or, assuming n is at least 2, you can stop when the denominator is 2, and use the symmetry about 1/2 to fill in the rest of the terms.

For the particular purpose of finding the best rational approximation to a real number x with denominator < N, Chrystal's Textbook of Algebra describes a method.

[Kebbaj]

The existence of a 5,5 solution is still open.

[Kebbaj]

Approximation is a science. Useful science.

The exact is not always possible.
When we say that god does not play gods, it may be true, but we are not god!
At the infinitely small the 0 joined the 1 but it must be god to see it.
Taking the example of Farey Secance and the problem of February. The number 0 as a solution is difficult to conceive:
- If you cut an orange you have pieces of oranges! Okay.
- If you do not cut it, it remains intact Solution 1! Okay.
- But how do you design solution 0?
do you dislike her?
Yet you are telling the 0 solution in your February answer !.

[SmartMersenne]

Originally Posted by Kebbaj

When we say that god does not play gods, it may be true, but we are not god!

I have no idea what that means (or the rest)

Did you mean to say "God does not play dice"?

[Kebbaj]

The interpretation is free.
The approximation gives your answer Exactly.
Thank you.