Problem 2838. Optimum Egyptian Fractions
Given fraction numerator A and denominator B, find denominators C for Egyptian fraction. The goal of this problem is to minimize the sum of the list.
A = 16; B = 63; % 16/63 == 1/7 + 1/9 C = [7, 9];
C may be [4, 252] or [5, 19, 749, 640395] or [5, 27, 63, 945] or [6, 12, 252] or [7, 9] or almost any else of infinite more other options. The best one is [7, 9] with sum 16.
- You may assume A<B,
- Your score will be based on sum of answers,
- No cheating, please,
- While greedy algorithm usually solves this problem, score may not be satisfying,
- Class of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.
- I'm open for proposals to improve test, i.e. verification of output which is far from perfect.
Solution CommentsShow comments
Problem Recent Solvers15