Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi test

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!

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

Created by Muthu Annamalai

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;

        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.


  2. AMS blog post by Tyler Clark (@tylermath12)
  3. 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

Problem Group

Solution Statistics

17 correct solutions 11 incorrect solutions
Last solution submitted on Apr 12, 2016

Problem Comments

Solution Comments