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

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
  1. http://en.wikipedia.org/wiki/Egyptian_fraction
  2. AMS blog post by Tyler Clark (@tylermath12) http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/
  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

Solution Stats

32.5% Correct | 67.5% Incorrect
Last Solution submitted on Apr 27, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers71

Suggested Problems

More from this Author10

Problem Tags

Community Treasure Hunt

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

Start Hunting!