You can solve the question very fast with appropriate precomputed values.
The sequence is known as the Stern-Brocot sequence, I was not aware of it before!