Cody

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

33.33% Correct | 66.67% Incorrect
Last Solution submitted on Aug 30, 2017