Project Euler Problem 71 and Stern-Brocot tree

Project Euler Problem 71 describes as follows:

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

Such sequences can be included to be a Stern–Brocot tree

It all starts with fractions and the number line. We start off with the interval [0,1]:

Now let’s play a little game. We’re going to take the fractions 0/1 and 1/1 and calculate their mediant by taking the sum of their numerators and denominators to get (0+1)/(1+1)=1/2:

With this new point on the line, we can do this mediant operation again to get (0+1)/(1+2)=1/3 and (1+1)/(2+1)=2/3:

Another iteration of this process gives:

But we can continue this process indefinitely! And instead of notating these fractions on the number line, we can put them into a tree:

Now of course, merely having fractions between zero and one isn’t satisfying enough, so we extend the construction of this tree to begin with the points 0/1 and 1/0, as nonsensical as that may sound. Then we get something like this:

This is the Stern-Brocot tree.

Here we use the subtree which root is 1/2:

We need to find a node between 2/5 and 3/7. first, take numerators as [2, 3], denominators as [5, 7]
so we can find a node between 2/5 and 3/7, that is . Then iteratively we use the same strategy to find a node between 5/12 and 3/7. When we reach the condition that denominator > 1000,000, loop terminates.

Here is the code using coffeescript:

1
2
3
4
5
6
7

[n, d] = [2, 5]

while d <= 1000000
	n += 3
	d += 7
# go back if we exceeds 
console.log n - 3

Reference: http://hxhl95.github.io/stern-brocot-tree-part-1/

事实上，可以证明：
如果，则
证明如下：
由 可以得到：，那么
即① < ③

且：

即③ < ②