Problem 2838. Optimum Egyptian Fractions
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 non-greedy 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 ...
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, non-zero values (also non-uniity values assuming A<B). Algorithms for this are well-known 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
Inefficient as all get-out, but it appears to be guaranteed to terminate with an optimal solution per the provided metric. Am I missing something here?
Problem Recent Solvers14
Find state names that start with the letter N
Sorting integers by their digits (Level 2)
More from this Author40
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!