We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #71: Ordered fractions
Project Euler #71: Ordered fractions
Contest ends in
Sort by
recency
|
13 Discussions
|
Please Login in order to post a comment
Here is my solution. Super fast in python 3
Find my java solution here
别看下面几位大爷的瞎BB。
(b*N-1)/(N*X) is a fraction less than b/a. Take the k step continued fraction of the fraction and calculate the denominator of the fraction represented by the continued fraction. Use Binary Search for k in range(1,32).
For those who became interested in Stern-Borcot due to this problem, just a note that studying the repeated application of it's recursive formulae can lead to quick algorithms (including for this problem, no GCD or modular inverse required), and also useful approximations. For example, my computer cannot tell the difference between M_PIl (pi as an f64) and 8717442233 / 2774848045, but also 355/113 is probably "good enough" in many cases (too large by 0.0000085%).
A related tree is the Calkin-Wilf tree. I recommend the paper "Recounting the Rationals" for those intrigued by Stern-Brocot. It's a very short, accessible, and intersting paper.
https://www.math.upenn.edu/~wilf/website/recounting.pdf
Floating point comparison is disastrous. Use algebraic comparison.
I followed the recommendation of others and looked up Stern-Brocot tree, Farey neighbours. However, even though I believe I've sufficiently implemented those approaches, it is still TLE #16-#20 in Python.
Farey neighbours seemed promising with an elegant expression like , but it somehow could not pass all test cases.
My latest implementation was even optimised with logarithms and extensively used continued fraction representation. When binary search along the Stern-Brocot tree was too slow for an input like
3 1000000000 1000000000000000
because of occasionally looking forgcd
to get mediants, I switched to first finding the continued fraction representation of the parent, and get the neighbour fraction from it (the parent itself or the left branch of it whichever applicable).I don't know where and how I could further improve my solution, consider it gives result for
3 1000000000 1000000000000000
in about 1 second.EDIT: One of the test inputs that requires more time:
100010627 100010633 1000000000000000
.EDIT 2: Got a very fast solution making use of the concept of Farey neighbours and modular inversion (implemented with Extended Euclidean Algorithm, which I just copied from somewhere else). It looks mythical to me that just with the property , we could get to the answer in a blink of an eye. Very useful when the denominator of input is large. As I know nothing about modular inversion, will definitely come back to it after some reading.