"We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first ``local'' phase, a classical search algorithm is used to produce many desirable constructions. In the second ``global'' phase, a transformer neural network is trained on the best such constructions. Samples from the trained transformer are then used as seeds for the first phase, and the process is repeated. We give a detailed introduction to this technique, and discuss the results of its application to several problems in extremal combinatorics. The performance of PatternBoost varies across different problems, but there are many situations where its performance is quite impressive. Using our technique, we find the best known solutions to several long-standing problems, including the construction of a counterexample to a conjecture that had remained open for 30 years."
Thanks for sharing. Very interesting. Added the formula to my fibonacci number algos collection at https://github.com/alidasdan/fibonacci-number-algorithms . Though simple, the new formula runs much slower than even the linear-time algo.
There are a couple of well-known algorithms to find the best rational approximation to a given real number. A good and short book is "Diophantine Approximations" by I. Niven. For code, you can also check out this repo of mine: https://github.com/alidasdan/best-rational-approximation .
Note that decimal numbers represented as a floating point numbers on a computer are actually rational numbers due to limited precision. So converting decimal numbers to fractions, both stored on a computer, means converting a fraction with potentially large numerator and/or denominator to a simpler fraction, say, one with a far smaller denonimator.
For example, an approximation to pi is 3.14159265358979323844, which is the same thing as 314159265358979323844/10^20 (trivial approximation). Using these algorithms we can covert this fraction to a simpler fraction under different approximation criteria such as a bound on the approximation error or a bound on the magnitude of the denominator. For this example, we then get various approximations to pi such as 22/7, 355/113, ...