Problem 2838. Optimum Egyptian Fractions

Created by Jan Orwat

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Following problem was inspired by</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm\"><w:r><w:t>this problem</w:t></w:r></w:hyperlink><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542\"><w:r><w:t>that comment</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given fraction numerator</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>A</w:t></w:r><w:r><w:t> and denominator</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>B</w:t></w:r><w:r><w:t>, find denominators</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>C</w:t></w:r><w:r><w:t> for</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Egyptian_fraction\"><w:r><w:t>Egyptian fraction</w:t></w:r></w:hyperlink><w:r><w:t>. The goal of this problem is to minimize the sum of the list.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ A = 16;\n B = 63;\n % 16/63 == 1/7 + 1/9\n C = [7, 9];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>C</w:t></w:r><w:r><w:t> may be</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[4, 252]</w:t></w:r><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[5, 19, 749, 640395]</w:t></w:r><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[5, 27, 63, 945]</w:t></w:r><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[6, 12, 252]</w:t></w:r><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[7, 9]</w:t></w:r><w:r><w:t> or almost any else of infinite more other options. The best one is</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>[7, 9]</w:t></w:r><w:r><w:t> with sum 16.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>You may assume</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>A&lt;B</w:t></w:r><w:r><w:t>,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Your score will be based on sum of answers,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>No cheating, please,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>While greedy algorithm usually solves this problem, score may not be satisfying,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Class of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>I'm open for proposals to improve test, i.e. verification of output which is far from perfect.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Following problem was inspired by <a href = "http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm">this problem</a> and <a href = "http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542">that comment</a>.Given fraction numerator A and denominator B, find denominators C for <a href = "https://en.wikipedia.org/wiki/Egyptian_fraction">Egyptian fraction</a>. The goal of this problem is to minimize the sum of the list.Example:<pre> A = 16;
 B = 63;
 % 16/63 == 1/7 + 1/9
 C = [7, 9];</pre>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.<ul><li>You may assume A&lt;B,</li><li>Your score will be based on sum of answers,</li><li>No cheating, please,</li><li>While greedy algorithm usually solves this problem, score may not be satisfying,</li><li>Class of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.</li><li>I'm open for proposals to improve test, i.e. verification of output which is far from perfect.</li></ul>

Solve

Solution Stats

25 Solutions
6 Solvers

Last Solution submitted on Aug 26, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Rafael S.T. Vieira on 18 Aug 2020

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.

Rafael S.T. Vieira on 18 Aug 2020

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.

Problem Recent Solvers6

Problem Tags

Problem 2838. Optimum Egyptian Fractions

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author41

Problem Tags

Problem 2838. Optimum Egyptian Fractions

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author41

Problem Tags

Players