Problem 2838. Optimum Egyptian Fractions

Following problem was inspired by this problem and that comment.

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.

Example:

   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 Stats

34.69% Correct | 65.31% Incorrect
Last Solution submitted on Apr 12, 2023

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers15

Suggested Problems

More from this Author40

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!