Problem 2126. Split bread like the Pharaohs - Egyptian fractions and greedy algorithm

Created by Muthu Annamalai
Appears in 2 groups

Difficulty:Rate

Solve Later
Add To GroupÃ‚

How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.
Egyptian fraction is writing any rational number p/q in terms of unity fractions;
e.g.  
        3/4 = 1/2 + 1/4, OR 
            = 1/3 + 1/4 + 1/6
      13/48 = 1/4 + 1/48
Write a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,
    i.e.   egyptian_fraction( 13, 48) should return [4,48],
You can use simple greedy algorithm or alternatives.
References
http://en.wikipedia.org/wiki/Egyptian_fraction
AMS blog post by Tyler Clark (@tylermath12) http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/
Bonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.
P.S: Updated test suite to check for proper solutions only

Solve

Solution Stats

246 Solutions
77 Solvers

Last Solution submitted on Feb 22, 2025

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

David Verrelli on 26 Apr 2018

This problem is quite well constructed and described. However, per the WP article linked to, it is important to specify two additional requirements: 〔1〕 Denominators must be positive. This is not explicitly mentioned in the Problem Statement [although perhaps it's implied], and moreover it's not checked in the Test Suite. That means 3/4 = 1/(1) + 1/(-4) would be erroneously accepted. 〔2〕 Each of the denominators must be different/unique. That is enforced in the Test Suite, but there's no mention of it in the Problem Statement. —DIV

Jean-Marie Sainthillier on 16 Jul 2018

Can't submit a solution to this problem (temporary unavailability of MATLAB Service).

Dyuman Joshi on 29 Mar 2023

The test suite has been updated to include more robust checks on solutions and solutions have been rescored.

Solution Comments

Show comments

Group

Number theory

44 Problems
21 Finishers

Problem Recent Solvers77

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!