Problem 2838. Optimum Egyptian Fractions
Solution Stats
Problem Comments

3 Comments
FYI, there is no known algorithm for optimal Egyptian fractions. Therefore this problem should allow the trivial solution of p/q as 1/q times p, which is not currently (this could be the worst score, a penalty can be included for repeated denominators). The solution for this problem is a greedy one (which may produce huge denominators), or the combination of nongreedy techniques that breaks the problem into several smaller pieces and which may create a huge sequence. I hope that the author has tested for upper and lower bounds on the test suite numbers since he is requesting an unknown solution and random numbers.
And my advice is if you do find a solution for this which attends the general case, don't publish it here, write a scientific paper.
It's not a PRACTICAL algorithm (too much time and memory required), but ...
Known Algorithms/lemmas:
A) Define greedy(A,B) as Fibonacci's greedy algorithm solution, expressed as a vector of denominators. It is known to produce a finite list of finite integers for natural A and B. Its sum is therefore finite.
B) Define dist_part(n) to generate all partitions of the integer n with distinct, nonzero values (also nonuniity values assuming A<B). Algorithms for this are wellknown as well (and available for download). Let's have it generate a row cell vector of row vectors of integers.
Then, ignoring round off errors which can be resolved using big integer tools, this should constitute an algorithm:
function opt = optimal_egyptian(A,B)
for score = 1:sum(greedy(A,B)) % There is an upper bound
for each = dist_part(score)
opt=cell2mat(each); % make it a numeric vector
if sum(1./opt)==A/B
return
end
end
end
end
Inefficient as all getout, but it appears to be guaranteed to terminate with an optimal solution per the provided metric. Am I missing something here?
Problem Recent Solvers13
Suggested Problems

Find relatively common elements in matrix rows
1551 Solvers

Recurring Cycle Length (Inspired by Project Euler Problem 26)
98 Solvers

140 Solvers

44 Solvers

485 Solvers
More from this Author40
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!