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
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 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 ...
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, 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
if sum(1./opt)==A/B
return
end
end
end
end
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?
Solution Comments
Show commentsProblem Recent Solvers15
Suggested Problems
-
1227 Solvers
-
Find state names that start with the letter N
1249 Solvers
-
253 Solvers
-
Spherical radius given four points
237 Solvers
-
Find my daddy long leg (No 's')
2422 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!