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

15 Solutions
4 Solvers

Last Solution submitted on Jun 12, 2020

Last 200 Solutions

Problem Recent Solvers4

Problem Tags

Problem 2838. Optimum Egyptian Fractions

Solution Stats

Last 200 Solutions

Problem Recent Solvers4

Suggested Problems

More from this Author41

Problem Tags

Problem 2838. Optimum Egyptian Fractions

Solution Stats

Last 200 Solutions

Problem Recent Solvers4

Suggested Problems

More from this Author41

Problem Tags

Players